I have the same issue. I tried changing my max_input_vars to 900000 and still isn’t working. I lost half of my mega menu settings and it won’t let me resave them anymore.
UPDATE: I had made that edit in my webroot php.ini. I then contacted my host and they added a .user.ini in the wp-admin folder with max_input_var = 10000 and that did the trick!