I tracked it down to multiple calls to util_memoize_flush_regexp in workflow.
That procedure loops over all the util_memoize cache entries, in this case 400,000 of them, and performs several regexp on them.
This is obviously very slow. I don't recommend using this procedure in any busy site.
The 400,000 cache entries only take up 9mb so you can easily get a huge number of cache entries with a relative small total cache size.