They sound different, simply put, because Spanish is an evolving language. To address why could be difficult because there are many factors: isolation, exposure to other languages, development of local colloquialisms, etc.
There are several accents of both Colombian Spanish and Mexican Spanish, all with their own distinguishing characteristics (differences in intonation, pronunciation of phonemes, even the diminishing or deletion of some phonemes altogether) and to pinpoint direct causes is a bit tricky.
I once read that many of the differences in the accents of Latin America come from even which part of Spain the immigrants who migrated during the Colonial Era to each respective area came from (ie. some from Galicia, some from Sevilla, etc.) however I'm not sure as to what extent that influenced the two larger dialects in question.
Another factor is contact with local languages; both colonists in Colombia and Mexico came into contact with different native tribes and civilizations and those interactions gave way to different loanwords to each dialect, and perhaps even had an effect on the local accent. It is said that the s dropping phenomenon that occurs in many coastal dialects, including in Colombia, is a result of the influence of indigenous languages.
Isolation, however, is probably the biggest factor. Leave different communities separated by much distance with little contact for several hundred years and the dialects tend to diverge. The thing about language is that it changes to stay relevant to the population speaking it, and there are many socio-political factors that play into that. Now are they still very similar? Yes but there are definitely some notable differences, which you have noted by listening to Colombian dialects and comparing them to the more familiar Mexican dialects you have heard.
Now as far as tonality, I wouldn't say Mexican Spanish is tonal at all. Sure there are some interesting intonations in some dialects, but the concept of tonality (such as the one that exists in Chinese) implies that the tone of words has some effect on the meaning of the speech. In Mandarin, there are 4 distinguished tones that are attached to every syllable, such that a word will change meaning simply by changing the tone that you say it in.
I would agree that some Mexican dialects have some interesting intonation when compared to other dialects, but this is a characteristic of the dialect and doesn't actually have any effect on the speech. Compare the differences in some British dialects of English and American English; you will notice some degree of similarity.
Also if you are interested in hearing a more sing-song-y dialect of Colombian Spanish, look up the Paisa accent. You will notice an even greater emphasis on intonation.