I am happy I found this topic. I have been having the same problem. Since I updated to 4.6 I have lost all my menus and also all categories to my posts. I cannot create new menus.
This is not related to the theme I am using, because the problem persists when I switch themes.
It is not related to any plugins, because I tried uninstalling plugin not used much and also deactivated all the rest.
It still does not work.
The max_input_vars has been set to 9000 on the server, so this is not the problem either.
