Through fire, through water — if it's with you, I'll go anywhere.

Literal

Even-if fire [gen-の] middle, water [gen-の] middle. You [with-と-なら] where-[even-までも] go [polite-ます].

たとえ~でも 'even if X' is the concessive frame for hypothetical extreme cases — here the typically-suppressed でも is folded into the following 火の中、水の中 sentence fragment. 火の中水の中 '(through) fire and water' is the set idiomatic pair for 'through any hardship' — drawn from Japanese folk/heroic vocabulary. ~とならば is the formal 'if (it's) with X' conditional. どこまでも 'anywhere / to the ends of the earth' pairs naturally with いく.