cache_menu items are huge
I suspect that you have some very large menus in your site.  Rebuilding menus is a an expensive operation, and menu trees can vary page-to-page, user-to-user, etc.  As a result, that data gets cached in {cache_menu}.

My suggestion is to query in your favorite SQL tool, and print_r() the data column for the large entries to see if anything looks out of the ordinary.  In general, the data will be your menu tree with everything from the various hook_menu() entries added in.  Modules that add extra data onto menu entries (like Menu Attributes) will have there data here, too.

You need to profile to see where the problem is actually happening.

It could be the result of a less-than-ideally configured MySQL instance.  If you do have 1M cache entries, then you may want to bump up the query cache result set limit (I think this defaults to 128K).

You may also want to investigate using memcache or redis as your cache backend.

However, if you really do have huge menus, then the slowdown could be from unserializing all of that data.  If this is the case, then you need to figure out a strategy to cache the menu output when your pages are being built up.  Enabling block level caching may help, or you may need to make your own menu blocks, and cache that output yourself.  Panels caching may be worth investigating.

It may sound odd, but you may also want try to disabling caching for {cache_menu}.  The easiest way to do this is to install one of the dummy cache modules, and configure it to just use that cache backend for {cache_menu}.