I have been Facing similar Issue in WordPress
I am using a theme it is Portfolio, Logo carousel Slider apart it post and Menu
All have different categories menu itself a part of categories, Portfolio categories, logo carousel categories, sliders have too categories and it is not saving in the wordpress.
Sometimes it works but sometimes it is disappear.
I have deactivated all plugins but it wont works. Switched with different theme but it wont works.
I have been using such plugins
Better WP Security
Google Drive WP Media
Use Google Libraries
WP Fastest Cache
WP Really Simple Health
Problem are frequently. It sometimes works but sometimes it didnt.