It somehow seems like the wrong way to do things to me.
Could I suggest you create custom taxonomy for Artists and use a template for the taxonomy to list the first letters or list all the artists grouped by the first letter. It’ll be easier to add lyrics and manage in the long run.
Custom taxonomy would be a good idea but I’ve worked too much on the website as it is to change the complete logic of use. Also, it already includes around 200 artists, it would be too much work changing it. I’m sure the easiest solution is with wp_list_categories() but I do not know how to do it exactly.
Any way to count children categories?
wp_list_categories according to documentation does not list empty categories. Assuming sub-categories do not count as posts, then your single letter categories would not be listed, so all you will get will be child categories i.e. artists
So you should give that a try and see how it goes.
Haven’t tried it but you should also be able to do this with two queries. First to get the top level categories with the option depth=1, then use the results in a second query by excluding them.
That said, it’s still better to change the way things work before you get even bigger and any fixes become harder. It should be a pretty quick task to dump all current artists into a custom taxonomy and update their respective posts with a short php script.