How to deal with very large number of items in taxonomy

Hi. I am creating a lyrics website in Wordpress. I am using a custom post type called “lyrics” with artist, and album as taxonomies. And I have run into a problem. The artist taxonomy includes for now 6,000 records, which makes working with the add new (custom) post type (new lyric) extremely impractical because every time I want to add a new lyric, the page loads the entire artist taxonomy. Selecting a checkbox out of that taxonomy is essentially impossible. Is there a workaround? Something like adding a different taxonomy metabox that doesn’t load all of them? There is a plugin which adds autosuggest to the taxonomy box (like google search) which I have installed, but the page is still sluggish, probably because even with that plugin, the taxonomy still gets loaded in full. This is already impractical, and it will get completely impossible to work with adding new records when I add items to the “album” taxonomy.
Surely having several taxonomies with lots of items is not as uncommon. How do you deal with that when it exists?
Or, if possible, how would you do it differently?
As in, maybe use artist and album as custom post types instead of taxonomies, but this leaves me with the question of how to associate them and do things like “display all songs from this album” or “display all songs by this artist”, which I can easily do with the current structure where “album” and “artist” are taxonomies.

I wouldn’t put it past Wordpress to be running over 6K queries. I don’t really think Wordpress is the right tool for the job considering the amount of data you have already. You will either need to tune the hardware and/or add excessive server side caching. Data is stored very poorly in Wordpress which causes it to be extreme sluggish when scaling. There probably are some work-arounds but the better work-around is using the right tool for the job. Not to mention wordpress developers typically don’t think about scalability. So the more and more plugins you add the worse and worse the problem is likely to become.

Actually, the website is blazingly fast without any caching on the front end and on every other page except on the particular page for adding a new lyric post, so you’re wrong about it being a Wordpress problem. It’s just that the browser doesn’t deal very well with loading a <select> element with 6,000 items in it (the page source is 1.6 MB due to loading all those taxonomies at once). Scrolling the page is very slow and jerky. Kind of like it happens when running a page with a badly designed flash script. That’s why I was looking for an alternative to the taxonomy metabox. I did find one, but since the metabox still loads all of the items and the only thing it changes is adding the autocomplete metabox, the problem isn’t really resolved. If I could get it to retrieve the taxonomies from the database via Ajax without loading the whole <select> element, the problem would be solved.