We have 45,000 pages in our WP Admin. After around 20,000 we started noticing the time it takes to edit a page increased. What we're seeing now is that it's taking around 1 minute to fully open a page to edit it. Now all other areas of the site are running just fine. Editing posts are fast. It's only when editing a page that it takes a long time to open that page to edit it. We noticed that the more pages we have the slower that open edit page takes.
I'd say this is your key clue:
We noticed that the more pages we have the slower that open edit page takes.
Have you evaluated the plugins and custom scripts you are using? I'd start with deactivating all plugins, and if the issue clears up, reactivate one by one to isolate where the problem might be.