Although Alphanumeric filter links are generally a valid design pattern, I can't imagine someone enjoying browsing through 500+ items unless they're really bored. If I were designing this I'd go with categorized listing with search option.
In your case the categories could be Rock, Pop, Classic etc., perhaps with sub-categories. One frequently used design approach is to show the list of categories (often with icons), having the most popular / trending / featured titles prominently displayed, with the search bar at the top. This is what they do in Snapguide and Tumblr's mobile app.
Another example is Quora's search screen, which is mostly blank with just the search bar at the top and auto-complete as you type.
There are more ways, but the point is that with search, the list of song titles is narrowed down to just a few to a few dozen search results. You could then allow sorting by title, date, popularity etc. to complete the search experience.
You may still provide an option to browse 'all titles' using alphanumeric filters as an alternative option, just not as the default one.