We'll create fresh WordPress site with Faster Appearance – Menus installed. You have 20 minutes to test the plugin after that site we'll be deleted.
The new accessibility javascript in the Appearance > Menus panel in WordPress 3.6 can significantly slow the page load speed when using a large number of menu items (> 50). This plugin defers the accessibility processing to eliminate the scripting bottleneck and allow the Appearance > Menus screen to run much faster and more responsively.
This solution is fairly rough. Hopefully we can develop a robust solution that can eventually become part of the core. Pull requests through GitHub are welcome.