As far as an index goes, I would say:
alphabetical by title AND by first line
by album
by artist
and by any other way you can possibly think of indexing them. You can never,ever have too many ways of accessing data.
Make sure your copyright attributions and declarations are on EVERY page
one song per page is excellent. what many people forget is that a great many people still are using slower modems and to have to wait while an entire list of songs downloads, when all you may want is a single one is beyond painful.
please keep the site as "generic" as possible with regard to browsers. (on bended knee I beg you!)
MMario