In several previous posts, I presented words which have undergone phonological changes and thereby conceal their origins. Likewise, 만나다 has a surprisingly logical and simple origin which, although hard to spot, you will likely not forget once you know.
The spelling makes it difficult to notice, but 만나다 is actually a combination of "맞다 ('to greet, receive, accept, welcome') + 나다 ('to happen, occur')." Thus, 만나다 literally means something along the lines of "the occurrence of a greeting or welcoming." When 맞 and 나다 are placed next to each other, the pronunciation changes to 만나다 for the sake of practicality. As with many phonological changes of this sort, it simply makes the word easier to pronounce.
As an interesting side note, the adverb "마주 ('facing, face to face')" was also formed from the verb 맞다. Likewise, 마중 (to meet someone who has come, usually in the sense of picking someone up at a train station or airport) and words ending in -맞이 all share this common origin of 맞- and are related to meeting or greeting.
백문식. 우리말 어원 사전. 1st ed. 서울: 도서출판 박이정, 2014. Print.