Every language has exceptions to "rules". In fact, there are few hard and fast rules for any language, since every language is a mix of another.
But, once you get comfortable with a language, you can appreciate the differences and make interesting guesses about the exceptions' origins. It can be fun.
I like http://www.hanzicraft.com/ because it breaks down the characters into parts you can click on to get their definitions or origins. Hacking chinese also has a cool resources section here [1], categorized, so you can browse through dictionaries, listening tools, practice tests, browser add-ons, etc. etc.
https://en.wikipedia.org/wiki/Ateji
The ateji for Malaysia is 馬来, Horse, come, ma rai.
Nowadays loanwords are usually written alphabetically instead of ateji. フランス and マレーシア. The old way is still written for abbreviations; 仏 is the equivalent of writing "Fr" in English.
An interesting case is America (亜米利加)where the abbreviation is 米 (pronounced "bei") not 亜 (pronounced "a") because A is for Asia! (亜細亜).
As any one reading HN should know, naming things is hard...
So, Malay (ie, of Malaysia).
The first character of 馬來 is "horse" and the second is "come/arrive". So I was sitting there puzzling it out until I realised that if I pronounced it in Mandarin, it sounded a lot like "Malay" - which is in fact what it means.
Or you could be like me, idly sitting in a Malaysian restaurant, reading "馬來" and trying to figure what "Horses Arriving" has to to do with curry.