It seems to be a bug in WordPress. As soon as there are more than 50 pages, a hard-coded pagination limit in the WordPress Menus admin page, the pages listing is broken in terms of hierarchy and order.
traone at the bottom of this support thread fixed it in an older version of WordPress by changing a pagination variable in a core wordpress admin file, but I haven’t been able to find a similar variable in WordPress 3.5+
http://wordpress.org/support/topic/missing-pages-in-appearance-menus-pages?replies=6
I reproduced the problem on a clean installation of the 3.6 release candidate as well.
Didn’t see the variable because I was looking at the wrong file. Oops.
I think this is a cleaner work-around until the bug is corrected.
http://core.trac.wordpress.org/attachment/ticket/18282/18282-disable-nav-menu-pagination.patch