The biggest expense is all the index.c stuff to support IMAP protocol requirements. There's a lot of cost in there which will go away with JMAP, and which will go away even more when we replace the separate cyrus.index files with a structured database per user. That's still got a ton of work to do though... one of the goals for long term Cyrus improvements.
That's how I would expect a JSON based protocol to work for pretty much all types of requests that provide potentially large lists in a response. I would expect getMailboxes to work this way too to be honest.
One of our slack messages is something that's become a bit of a cliche! "JMAP will fix it" - in this case, a lot of the cost is generating the message counts by iterating every match, and that's not going to be cheaper in JMAP. We don't have data structures that allow sorted partial search responses, so we can't generate the first page until we've resolved the search for every message :(