I have iOS 10 with Photos library taking 32 GB on iCloud. It was taking 2 GB on my iPhone 6, which was all the space left. I tried to completely disable iCloud and delete all the photos. After one hour, the deletion has stopped, but the Photos library is still taking 800 MB! I tried to connect the phone to iTunes/Image capture, but with no effect. It seems to be empty, but it is not.
Check under Photos' Recently Deleted album. From the Albums view, it appears as a trash can.
Since iOS 8, photos that have been deleted remain on your phone under the Recently Deleted album and are automatically deleted after 30 days, or until you delete them yourself, after which they are permanently gone.
The images in this album still occupy space on your phone. To remove them, go into the album, tap "Select" in the top right corner, and then "Delete All" in the bottom left corner.