How to replace or delete entire iCloud photos library?
Since deleting directly in the browser did not work (I guess Apple never tested it with a library that large...), I ended up using this workaround: create a new Photos library (start Photos app with option key pressed). Make it the system library and sync with iCloud (only download previews). Then delete all photos and albums once the download has been completed. The changes will take about 15 minutes to be reflected in the browser.
Then I switched back to my original library and enabled iCloud sync. Now it's uploading all of the >40,000 images back to iCloud.