Renaming 37K topics could be done with a script. If you have a budget for such, post on Marketplace or contact me directly.
Re-training your users to guess new URLs, which would seem much harder. But how did you train them to guess URLs in the first place? Are they coming from some other site that you manage?