While 12MHz sounds weak, the heavy lifting was done by dedicated graphics hardware. Once you relieve the CPU from the burden of blitting, you're left with more than enough cycles for almost any sort of game. Even the GBA only had a 16MHz ARM! From Wikipedia:

"The SNK custom video chipset allows the system to draw sprites in vertical strips which are 16 pixels wide, and can be 16 to 512 pixels tall; it can draw up to 96 sprites per scanline for a total of 380 sprites on the screen at a time."

Memory was the big issue of the Neo Geo, if I remember correctly. The system itself was expensive enough, but what really broke the bank was the price of each individual game. And that was mainly because they used cartridges with many times the amount of ROM compared to what Nintendo or Sega used. That meant that a single game cost more than their competitor's console.

And by the time the Neo Geo CD came out where this was suddenly not an issue anymore, it was too late alredy...

The Neo Geo CD had 7 megs of RAM, and the Neo Geo cart games just kept on getting bigger. The last CD games released would often load midway through levels or several times per fight for fighting games. Then from there many Neo Geo games never got a CD release because it just wasn't feasible.

As for the price of Neo Geo games, just for some fun here is one that sold last week for over $5000: http://www.ebay.com/itm/Blazing-Star-Neo-Geo-AES-JP-import-1...

Many Neo Geo games are now in four figure territory.

Yes. I had a Neo Geo, but my parents would only buy the games used. The less-popular games got pretty cheap that way, so I mostly played a bunch of "odd" games rather than the huge hits like King of Fighters and so on. To give an idea of how big the games are, a Neo Geo cartridge is roughly the size of a VHS cassette and contains two circuit boards.

The game size was still kind of an issue on Neo Geo CD since it was only a single-speed drive. The system was kind of infamous for long load times. Think of the loading time of an early PS1 game, and then consider that Neo Geo CD had something like 3x the RAM to fill, a drive half as fast, and no good way to "stream" or otherwise hide disc loading. A few later games had to stop in the middle of a level to load.