Just encountered the same problem for the first time. I have a shared hosting account that runs on Linux. Here’s the solution that worked for me:
1. Go to Control Panel > Hosting > File Manager
2. Edit php.ini
3. Add max_input_vars = 3000 right after the following line:
url_rewriter.tags = “a=href,area=href,frame=src,input=src,form=,fieldset=”
4. Save the file.
5. Rename the file to php5.ini
6. Go to Control Panel > Hosting > System Processes
7. Click the “End Web” button
8. Now try adding more menu items on your WordPress site.