I ran into this situation myself. Here’s what I did to get my storage back…
If you’re using the PC/mac desktop “backup and sync” from Google try this:
Move/copy all your pics and vids out of the “picture” and “video” folders to a new folder on your desktop. Then delete everything in your Picture and Videos folders (make sure you have copied them off and of course have backups (like you should!) Log into Google photos and make sure they are deleted there as well and that your storage goes back down. Recheck your upload setting in the desktop app to match your phone photos app for “free unlimited storage” (as you say you have done). Now move the pictures and videos back from the desktop folder you made, back to their pictures and video folder on your PC and let “backup and sync” re-upload the files.
If your pics/vids are only on your phone: You’ll need to hook up your phone to a pc/mac and copy off all of your pic and vids. Once they are safe on the PC, go ahead and delete them from your phone which should sync with the Google photos in the cloud and will delete them there as well. Once Google phots shows your storage back down to almost zero you can copy the pics/vids back to the phone (to the folders you copied them out of) and re-upload your files. (I would make sure you’re using WiFi for this action and not your data.)
This should bring your storage back down. Good luck! And remember, have backups when doing something like this!