Don't worry, you're not the only one...
What I did to clear up my space was the following:
1. I went on iCloud.com and deleted all my photos and videos and emptied the "recently deleted folder" as well.
2. iCloud Photos reported 0 photos and 0 videos.
3. iCloud Photos storage occupied approx 1GB of data...
4. On my windows laptop I installed, iCloud for Windows and asked it to download all my iCloud Photos media.
5. Voila! Most of my invisible and deleted photos were downloaded to my laptop!
6. I then went and uploaded all those deleted photos up to iCloud.com.
7. iCloud Photos now showed all those phantom photos.
8. Deleting those files cleaned up the remaining used space...
Hope this helps you as well!
PS: What I think is happening (or what I think happened in my case) is that this is a bug... If for example I take 10 photos while being outside (no wifi), delete 5 of them and delete them from the "recently deleted folder" as well, when I connect agai to a wifi network, the backup process begins and the phone uploads all of them (all 10) to the iCloud but "hides" the deleted 5 due to a bug... What I did above was "overwriting" the invisible files... Just my 2c...