I think this is a bad case of taxonomy split introduced in WP 4.2
ref. https://make.wordpress.org/core/2015/02/16/taxonomy-term-splitting-in-4-2-a-developer-guide/
Solution for this would be to use this plugin to detect and fix the splitting before Updating menus which is a bit buggy in my opinion. Update nav menus will trigger “wp_nav_menu_update_menu_items” function which between split gives new menu 0 sub-items.