Posting from memory here as I don't have an MC in front of me...
you need something like this in the search bar, from a view that lists all of your audio...
[=ismissing([filename])]=1
I can never remember if it's [File Name] or [Filename]
The resulting list should be all files MC cannot find.
Pick one.
Right click > Library Tools > Rename files from properties
When the tool opens, the first field in the top left is a drop menu. Use that to select "Update library to point to a new location"
figure out the directory rule you need to show MC where the file is now. The "Before/After" info on the right will help.
Press OK.
Refresh you list and that file should drop off. Now you should be OK to go wholesale...
Select the entire list and repeat.
Now, having repaired the links, you can use the same tool again, only this time, the top left menu item to "move file if filename changes" or whatever it is exactly, to have MC move the files into ordered folders of your choosing.
-marko