OK, For myself, I just figured it out, and I don’t know if it will help the OP but it might help the next guy with my problem.
First, I selected all the clips I needed to relink, which was all of them. Then I would tell it to relink, it would give me a file name and ask me to find it, and I did, and it managed to use that to relink a large number of other clips. Then it would ask me again, and I would repeat the process.
The good thing is that for the 6 directories and approximately 500 or so sub directories, it only asked me about six times, as once it found the first, it figured out the path to the others.
I’m a beginner at Premiere, so I didn’t know it would do that, thought I would have to find 500 paths, and panicked. I posted on this thread instead of in the beginner section since it was related when I did my search on the problem.