512ms worth.. MP3's at 128kbps average about 1mb/min. Since songs are different length, I can only tell you that it will hold 512 mins or 8 1/2 hours of music at 128kbps.
If you lower the quality to, say, 96kbps you'll get even more music on there. Lower it again to 64kbps and you'll get 0.5mb/min or 17 hours. However, 64kbps might be of too low quality for you, so might be 128 - you'll have to try each and see which you can live with.
I normally find the average size of an mp3 to be around 4mb. Therefore you could expect around 120-130, give or take. If you can be bothered, you can convert the mp3's to wma and this will let you store double the songs. I could be bothered doing this normally, as even if im away somewhere for a week, 120 songs is usually enough. Just keep putting in and taking out what tracks ur gonna wanna listen to or what one your fed up with.