Photos on the Mac makes this trivial to accomplish. Similarly with the improved web interface, this is a two step process.
- Command A - select all
- Delete
- Select All Photos album
- File - Show Recently Deleted
- click the Delete All button in the top right
- be patient and wait for the deletion to happen everywhere and filter down to all devices that are syncing from the cloud
Photos for OS X released with 10.10.3 has the changes needed for easy cleaning:
- Open your Photos library that is the system library
- File -> Show Recently Deleted
- Select Delete All in the top right
- Repeat as often as needed if the app is still downloading new photos from the cloud
You can also delete 1,000 photos a time using the web interface in 2019 at https://icloud.com/#photos