All the songs have to be stuffed into a ROM. There's no optical media or a hard drive. 20 songs probably takes up about 200MB for the audio and any background animations. They probably used a 256MB ROM (given the above size), leaving 56MB for the game program, steps, interface graphics etc. It's a reasonable size. Mask ROMs are cheap, but not cheap enough that you can just go around putting 512-1GB ROMs in $20 devices. Also realize that any compression they use is probably very simple (likely MP3 since hardware decoders are cheap) as the processor running it isn't likely very powerful. This further squeezes size requirements.
A normality test: +++ATH
If you are no longer connected to the internet, you need to apply more wax to your modem: it'll make it go faster.
If you find this funny, you're a nerd.
If neither of the above apply, you are normal. Congratulations.