The full history of these words is somewhat interesting (to me at least). If you will indulge a somewhat long explanation ...
If we go back around 5000 years, our linguistic ancestors, the Proto-IndoEuropeans were living Western/Southwestern Asia. Their language, PIE, was a very sophisticated language, very different from anything that exists today, though many features of the language have survived.
One interesting aspect of PIE was that there was nothing like "prepositions" as they exist today. So, for example, in the English sentence "Go with me", the verb is "go" and the prepositional phrase "with me" modifies it. The pronoun "me" is the object of "with". In PIE, it was distinctly different. The pronoun would be the object of the verb: "Go me". The "with" would be what is called a particle word, which gives context to the relationship between "go" and "me". Word order in PIE (as with Latin, Ancient Greek, Sanskrit, and many other ancient languages) was much more free than in many modern languages, because of inflections in the nouns, pronouns, and verbs. So for this phrase the word order could look like "me go with", "with go me", "go me with", or other variations. There would be no loss of clarity. And again, the "with" would not be associated with "me" alone but would be associated with "me" and "go".
In PIE, the word for "me" was *hme (or *me depending on which scholar you ask). The word for "with" was *kom. In Latin these words became "me" and "cum", respectively. What appears to have been the case, at least for the PIE ancestors that reached Italy, was that placing *kom after *hme (and other accusative pronouns) was especially common. In other words, "*hme *kom", "*te *kom", etc. would be the most common word ordering. It was, in fact, so common that it stuck in Latin: "me cum", "te cum", etc.
Now, what is interesting here is that, in Latin, the concept of particle words virtually disappeared entirely (whereas they still exist to a great degree in German, English, and some other languages). In Latin these particles changed into strict prepositions and adverbs (in most cases). So the particle word *kom became the preposition "cum". And as with all prepositions in Latin, all prepositional objects of "cum" come AFTER the preposition. So logically "with me" should be "cum me". However, as mentioned, the word order "me cum" was highly ingrained in Latin from its ancient history, despite this violating the prepositional rule. So what happened in Latin was that "me cum" became an adverb "mecum" (and similarly "tecum", "nobiscum", etc.). By making it a single word, there was no violation of the prepositional rule. Hence these odd little adverbs that existed in Latin throughout Antiquity.
Then we come to Late Antiquity and the early Middle Ages. The Western Roman Empire has brought in huge numbers of foreign tribes, the Goths in particular, to man its armies and perform other functions that the Romans do not want to do. Although these tribes live in the Empire, they are not granted citizenship and are segregated from the Romans themselves. They learn Latin, but very bad Latin. Some scholars have described the language they developed as a "creole" of Latin and Gothic, i.e. inspired by Latin but not really Latin. These tribes eventually overthrew their Roman masters and hence we have the Middle Ages. The languages that emerged in much of Europe really evolved from this "creole", not really Latin proper. In this creole, there were many rapid changes to the language, some uniform, some regional. One that occurred was that, because "mecum" seemed to violate the standard rules of Latin, the Iberians hypercorrected this to "cum mecum" ("with me-with"). But, of course, as that was not quite right either that quickly became a single word, "cum-mecum". And then, as the Iberian languages evolved, this became "conmigo".
Hope that wasn't too long-winded.
