Sometimes you just need to update the menu information in batch using SQL. use the following to find where this information is held.
Menu by itself is a taxonomy in WP. It means that you can find all menus in wp_terms table, by running following query:
SELECT * FROM wp_terms AS t LEFT JOIN wp_term_taxonomy AS tt ON tt.term_id = t.term_id WHERE tt.taxonomy = 'nav_menu';
Menu item is custom post type in WP. They are stored in wp_posts table. You can find all of them by using this query:
SELECT * FROM wp_posts WHERE post_type = 'nav_menu_item';
Relations between menus and menu items are stored in wp_term_relationships table. To find all items of specific menu you can use this query:
SELECT p.* FROM wp_posts AS p LEFT JOIN wp_term_relationships AS tr ON tr.object_id = p.ID LEFT JOIN wp_term_taxonomy AS tt ON tt.term_taxonomy_id = tr.term_taxonomy_id WHERE p.post_type = 'nav_menu_item' AND tt.term_id = /*your menu ID*/;