According to Japanese Wikipedia, the pronunciation of American was メリケン during the Meiji period, and was rendered into kanji as 「米利堅」
Since the first character is 米 （べい、まい、めい） the abbreviation became 米国. This was despite the fact that the full kanji representation of アメリカ is 亜米利加. I suspect it was because 亜 is already used to represent Asia.
Similarly, the Meiji era phoneticisation of England was エイギリ or 英吉利 in kanji. Taking the first kanji of this for the abbreviation we get 英国.
Since England is also synonymous in Japan with Great Britain, 大不列頓 or だい-ブリテン was also used (in Meiji times, not now)
Here is a complete list of (nearly) all countries foreign to Japan and their corresponding kanji-fied versions.
Very interesting link that one.