Agreed. Heck, isn't the el- also redundant in Hungarian as well? I get that it adds the meaning of "away", but költöz kind of implies that anyway, unless you were moving to America from within America itself. (But then you'd get some weird looks from people if you said "I'm moving to America")
I'd say Elköltözünk Amerikába but Amerikába költözünk.
By putting the verb in the front it gets emphasised, I think that's why the prefix suddenly appears. I'd expect someone to simply say "költözünk" without a prefix if I asked them why their house is full of boxes and suitcases. But if they just randomly announced that they move to America, they'd use the prefix.
If Amerikába is in front, adding the prefix is not only redundant, but unnatural.