Magnus - I checked out your tool, but it looks like you're using a query against the categorylinks table? Have you played with setting up a new table for categories and fulltext indexing it? Use group_concat to get all of a pages categories into one field, then create a fulltext index on that field. You get much better performance than using the categorylinks table (kind of weird, eh?) Are you pinging a live database, or a copy made from a dump? (please excuse my ignorance if this is common knowledge)
I'm working on dummying up a UI using the same approach (fulltext index of categories) on wikidweb and will write back when I've got something worth looking at...
Best Regards, Aerik