@Davydov:
1. A test project is fine,
however, instead of doing 100 works, do 10. I say this because the purpose of it is for me to understand the general structure; whatever pages end up being done will have to be re-done when the tagging system is in place, because the technical solution for that is significantly different. You can choose the pages to do, and document which pages are done. Post the link on my talk page and I'll check it out.

2. Now I understand your insistence on having fine categories. My opposition was not towards your idea, but towards the implementation. Now that I know why exactly you want these combined categories, I fully support you wanting other people to be able to list the combinations for which there actually are pieces.
However, there is a better way to achieve the same goal without actually having to create categories for the purpose.
So, instead, I will write a "Category Walker" special page. What it does is that it lists the other categories that are included in the pages in that category. For example, a category walk for "Sonata" may show up "Violin and Piano (20)", "Viola and Piano (5)" and etc (the numbers being the # of pages that are in both the "Sonata" and the other category). The benefits of this system are its flexibility (you don't need to walk only a genre/instrumentation combination; you can do it for any combination of categories, for example, a large composer category) and its malleability (I can change the entire system very easily via programming if there are problems).
3. I read your last post, and I wanted to express concern about using instrumentation categories that are too detailed. I am not opposed per se, but I think we should think about whether this system is supposed to replace the level of detail for the "Instrumentation" field on the page (except, of course, for the orchestral pieces which vary wildly), or whether it is supposed to be an abstraction of general instrumentation types. I am not hugely concerned because the tagging system will be able to combine categories should there be too many, but it is something that might be kept in mind. If it is expedient or necessary to do so, I do not mind revamping the instrumentation classification in the process. This is not a question that needs to be answered right now, though I would suggest putting a limit on the number of instruments for which there is a detailed category (i.e. any instrument combination above that number will need more generalized categories). But ultimately I leave the decision up to the librarians. However, I would like to hear your thoughts on this right now so I can better understand the system.
@Everyone else:
Now that I think I have a handle on what exactly the tagging system is about, I will describe the technical solution. It may sound strange at first, but I believe it is the most efficient.
There are three core components:
1. Tag resolution system. This system consists of two parts: (a) a tag translation page (TTP) in the style of normal translation pages (e.g. Mediawiki:FTE:composer:Messages and co.) (b) the mechanism inside #fte:imslppage which resolves the tag into actual categories. So, for example, a tag might be like "|Tag=SON, VLNP" on the work page, the corresponding TTP section being "*SON|Sonata" and "*VLN|Violin and Piano", the entire thing resolving into "[[Category:Sonata]][[Category:Violin and Piano]]". The reason for this translation is twofold: (a) it deters people from messing with the system (plus, the translation page can be locked to prevent tag creation by normal users), and (b) it allows for very cheap renaming and combining of categories, which is a huge plus because we cannot foresee what will happen in this project and people may well disagree or change their minds later. Additionally, a tag may be tied to two categories if necessary (e.g. "*SON|Sonata|Chamber works" = "[[Category:Sonata]][[Category:Chamber works]]"), and there is huge leeway for all sorts of different interpretations and tricks that one can do with tags.
2. Category intersect system. Basically this will be a modified version of the current system, adding two functionalities: (a) can intersect more than 2 categories, and (b) can do negative intersects (i.e. intersects pages not in category X).
3. Category walker. Basically what I told Davydov above. This will be combined with the category intersect system to create a fully and automatically navigable category system.
There are also a few optional components in planning that may make the entire project more pleasant to work with, but they are not essential to the project.
Any suggestions/comments welcome.