Hiya George,
To do what you're wanting to do wouldn't be too difficult if you have experience with find/replace within any kind of editor be it just a text editor (not a MS product unless it's just plain Notepad) or in an HTML Editor.
You would first need to create your new menu of course, whatever type you plan to make so that it's completely finished. Test it on a page so you know exactly how to install it into the page.
Once you know how to put it where you want it etc. Then it's a matter of just doing a Search & Replace which there are some programs which will do multiple pages at the same time. I'm unfortunately not sure which ones they are at the moment, but I would think someone else will know, or that a Google search for "mass find replace" would find something suitable.
With that many pages, you might find it more beneficial to use a PHP include or a Server Side Include setup so that you can alter just one page for the menu and it will update all pages. This would give you much more control over your menu and a lot less work later if you decide to add things to your menu or change a name or link etc. Especially if you reference anything outside of your site that could end up going offline at some time in the future creating a dead link.
You could then just do a mass find/replace and just replace with nothing at all which would sufficiently remove whatever you have in the find box. You may need to do a find/replace for sections of the menu at a time as I don't know how much text a program will allow you to input into the find or replace.
Just some food for thought.