I guess there shouldn’t be that many items in a menu in the first place, but sometimes it may be a necessity. This is not a WordPress issue as such it is more a hosting/PHP resources problem. The issue is a function in PHP called max_input_vars and its default value is 1000, by changing this value to 2000 normal service is resumed. The value is changed in your php.ini file.
Just add on a new line or edit if existing.