When you have a folder with 4,000 files in it, it will never be easy, but using naming scheme in Tag&Rename on similarly named songs to correct them would be the easy choice. This program is not free though, but it handles anything you throw at it.

Mp3 tag editor - Tag&Rename

e.g. songs that are properly tagged and have Artist and Title tags filled in correctly, use rename files "%1 - %2" which will make the file name "Artist - Title"

Remember to preview everything before saving.