But those prefixes can be explained. You are right, of course, that this happens all the time in linguistic history. It is called reanalysis. However, it seems unlikely in the specific case (an article is a good candidate for a prefix of this kind, a preposition less so: It marks changing syntactic functions so has a lot less stable recurrence). Also, unneeded.Just because there's no reason for it to happen doesn't preclude it from happening.
There's a possibility that phrases such as "vamos a Marclandia" could have become "vamos Amarclandia" as words or phrases were mistranslated into English.
Consider, "vamos a cazar el lagarto." ("We are going to hunt the lizard.") Later, "el lagarto" became "alligator" in English. "Vamos a cazar alligator." ("We are going to hunt alligator.") This also happened with words moving from French to English ("a croix" becoming "across"). It also happened the 'other way round' with, for example, "natter" (German for adder) becoming "adder" in English as "a natter" became "an adder."
None of these prefixes were added deliberately, but language just sometimes does things like that.