Ich geh mit mir von Ost nach Süd
is nothing you would usually say. It's part of the lyrics of the song Mein Land by the band Rammstein.
It's not a normal German sentence. So the question
What is the difference between "Ich geh" and "Ich geh mit mir"?
can not be answered in a grammatical sense. You need to interpret it considering the rest of the lyrics and you better try to do that yourself instead of asking for the interpretation of others. Let me provide some hints to make it easier for you:
Ich gehe mit dir ...
(I go with you ...)
is a normal German phrase. It's inviting and connective.
Ich gehe mit mir ...
is quite the opposite, especially since it doesn't really make sense. As @KilianFoth mentioned in a comment: provoking the kind of question you're asking might be the precise purpose of using this construction.
Ich gehe mit mir ...
is (considering the rest of the lyrics) everything but inviting. It's not about loneliness here, it's about separation.