Obviously, this is non standard WP behaviour, so tons of things could be wrong, but there are some ways to track down the error. The most important thing, I think, is the fact that storing the menu through the customizer works. This means that the function which does the storing of single menu items wp_update_nav_menu_item is functioning correctly, because this function is called directly from the customizer.
The path from the menu page to this function is different, namely through the function wp_nav_menu_update_menu_items. Given that things only go wrong once you want to save the menu, something systematically screws up while executing this function, which is not very complex:
- Read the current menu as stored in the database
- Loop through all the items in the
$_POSTvariable and callwp_update_nav_menu_itemto store them one by one. - Delete all menu items that were stored in the database but were not in
$_POST, so presumably were removed by the user
Under 2 you see a double foreach loop involving multidimensional arrays, which explains why things can get out of hand memorywise (which is why you see the wp_defer_term_counting function at the beginning, to save some memory). My guess would be that memory problems leads to empty values of the $args variable passed to wp_update_nav_menu_item and hence faulty menu items. Since menu items are posts in the database a screwup could even lead to the metadata of a page (also a post type) being wiped when the ID of the linked page is passed in stead of the menu item ID, even though there is a test for that at the beginning of wp_update_nav_menu_item.
These days WP needs a 128 MB memory limit, so you should raise that. In my experience 64MB leads to unexpected results regularly.
If that’s not possible or doesn’t work, there’s a workaround. There is a third function you can use to call wp_update_nav_menu_item: wp_save_nav_menu_items. This is an ajax-call that you can build into the menu page to save menu items one by one in stead of having to save the whole menu at once, thus evading memory issues. That would involve adding save buttons to every menu item and removing the general save button. There’s a lenghty tutorial here. Not an ideal solution, but if you cannot solve the server issue it could help.