The previous answers propose editing core WordPress files, which is never a good idea, as new versions of WordPress will overwrite the changes (among other things).
While the original Trac ticket #18282 has been open since July 2011, the issue still exists in WordPress 4.6 — going on 5+ years now.
Fortunately there is a “safe” way of implementing a workaround to change the behavior without hacking WordPress core.
Sergey Biryukov, a core committer, wrote a small feature plugin that changes the Pages metabox behavior and preserves the hierarchy for both post types and taxonomies:
Preserve Page and Taxonomy Hierarchy on Edit Menus Screen
The plugin only affects the “View All” tab, not “Most Recent” or “Most Used”, but is a much more maintainable and responsible solution than patching core or hacking the files directly.