It depends on how long the songs and how big they are, I have and 80G and I roughly put 8,700 songs on it with about 1-2mb left.
I rate close to 20000 hey. i used to have a 20gb and it had 5000 on, so do the math. @ 128kp/s, mp3 format
You have a 80gb with only 8, 700 songs on it? That sounds awful low for an iPod that is supposed to hold 20, 000. I know it depends on the length of your songs but I figured that you'd at least get 16, 000 or so.