What about grouping the artists in sublevels for each letter in the alphabet?
I mean, you open the artists list and all that you see is a list of the alphabet (plus a # for numbers). Then, you touch a letter and it displays the artists starting with that letter (cascade-like and in the same list). I believe it would be helpful even for those that have a great list of artists with 10+ songs each.