Install the Nuke extension and go to town.
I will check it out - Thanks for the pointer.
If you had a backup of your database, you could just restore it.
The corruption was discovered months after it happened, with multiple backups in between.
The titles seem to have invalid UTF-8 sequences in them. I'm not sure how it's possible to create such titles, in any version of MediaWiki.
This happened a couple of upgrades back, while the site wasn't being used. I have no idea what version was running at the time.
cleanupTitles.php will rename all the pages to valid titles. You can then use deleteBatch.php to delete them.
I now know what is on my schedule for this weekend. :)
Thanks to both of you.