I've never done this using v12, but what you describe is exactly how I would have gone about this job, and I would have expected the job to be done in a matter of minutes.
Find/replace works like so:
If the files are, as far as MC is concerned, 'missing', (MC places the 'broken link' red cross icon beside the file) then the find and replace tool can be used to fix the broken links provided you kept the same base directory structure when you moved the files. In this scenario, you are correct in your assumption that the changes are 'database only', and when the job is done, MC rechecks the database entries, finds the files, and so all the broken links are now fixed.
If the files are not missing, and you use the find/replace tool to make a change to the [filename] field, then MC will physically move the files from their existing location to the location you have specified in your find/replace command. For 90000 files, this would take an age and a day to complete.
Moot points now as you appear to have things sorted now, but probably worth mentioning anyway:
The only 2 things I can think of that would interfere with this entire process are MC's Auto-Import, and/or the settings under "Fix or Remove Broken Links".
If auto-import is watching the m: drive, and you have the 'fix or remove broken links' option set to "Yes", then the auto-import system would most likely be systematically removing the 'missing' files from your library, and likewise, if you've set it to watch the e: drive, it will be automatically importing those files as new library entries, probably at the same time as your find/replace job is running, creating an awful mess in the process.
If you know your library well, you can verify this by checking the import date of your files. If files that you know you imported 5 years ago are showing up as imported days ago, then 'auto-import' is the culprit for sure. If this turns out to be the case, turn off the auto-import system, restore from a 'pre e: drive' library backup and try your find/replace task again.
If the fix or remove broken links option is set to leave network files, then it's possible that MC is scanning the network for the files it expects to find on m: before making each 'find/replace' job. Try just setting this option to simply "No" while you get the job done.
-marko.