The special page was rewritten in MediaWiki 1.23 to make it usable on wikis the size of Wikipedia (commit 87be24db / https://gerrit.wikimedia.org/r/#/c/110299/ and some follow-up changes). Unfortunately this optimization for massive wikis seems to have caused the performance to suffer on smaller ones a bit.
(I have no answer to your problems, just saying this. :( Perhaps it helps someone else help you.)