After finding there’s a performance regression in sqlite I finally found some time to pinpoint what exactly regressed. While I’m not 100% certain that the query I used for this is exactly the one Quassel uses, it is very likely.
It turns out in newer versions of sqlite the query planner wasn’t using an index present in Quassel’s database for sorting but instead used manual sort. And this slowed it down noticeably. Since reporting this issue it’s been fixed and will be included in the next release versioned as 3.8.7. When it reaches Utopic I can unlock sqlite from upgrading on my machine :)