Per quanto riguarda il db hai usato relazioni? Mi sembra superfluo ed inutile creare tante tabelle quante sono le categorie...

Per quanto riguarda il numero dei link che devono comparire in una pagina, non sono in completo disaccordo con il tuo cliente.
Infatti se ci fossero state 300 canzoni di una categoria, nella tua pagina avresti visualizzato in sequenza tutte le canzoni? e quanto sarebbe stata lunga la pagina da scollare?

Tutti i siti con db hanno la cosiddetta gestione delle pagine, come anche questo form di html.it, cioè vengono presentate tot righe per pagina, poi si passa alla pagina successiva tramite un bottone next o si ritorna tramite prev.

Per semplificarti la vita, se usi mysql, esiste una parola chiave per le select che si chiama LIMIT, che ti permette di estrarre dal db tot tuple e non tutte.

Spero di esserti stato utile, ciao.