That is one hell of a menu. Would be good if we could actually improve the menu system. Have you looked into that? I've been on the verge of bringing this up for a while.
The issue we have with the menu is the exact same issue we had with the aliases until 4.7. We load the entire path alias into memory on every load.
Past tense.
We've replaces the one big load by a plethora of small loads. I am convinced this isn't a an improvement in all cases. E.g. on drupal.org, we got plenty of memory to burn, so the old setup probably wasn't much of a problem.
Memory was an issue, but not the main one. The main issue was using PHP to create an associative array for every page load, which bogged down everything. I installed the backport of the 4.7 patch for a client who has a dedicated SMP server with 2GB of RAM and it made a world of a difference there. You can see the statistics here: http://baaheyeldin.com/click/593/0 I agree that some scenarios (e.g. a sitemap page) where there will be a lot of small queries, but for most pages, this is not the case, and a bottleneck has been removed.