I had this last year. A week after turning on iCloud Photos Library the albums and photos disappeared, but all 36000 photos were still there.
I cleaned out iCloud Photos as you say (but you can delete from "recently deleted" on iCloud.com so you don't have to wait 30 days, but still a slow process). I waited a few days after emptying it to check that the iCloud Photos Library was completely empty. Signed out of iCloud and back in.
Then I restored the Library from a back up before they had disappeared, and all was well. Folders and Albums restored. Turned iCloud Photos Library back on.
Two weeks later same thing happened....Folders and Albums all gone.
Restored again, but left iCloud Photos turned off.....no problem now for a year.
The above all happened on my brother-in-laws computer, and I provide him support. My own iCPL has been fine for over two years.
One difference is that his Photos Library was converted form an iPhoto library going back to the very start of iPhoto, with loads of iPhoto upgrades then conversion to Photos. Mine was a fresh start. May not be a factor....just suspicious. I have seen a handful of reports of the same happening, but it is not a widespread problem. I have not seen any resolution.
Is your Photos Library an old iPhoto one?
Keep us posted how it works out for you, and keep backing up!