Relevant section from the manual: https://support.apple.com/kb/PH21294?viewlocale=en_US&locale=en_US
Summary: you can delete photos/videos through Photos/iCloud (https://icloud.com), but they are not removed immediately. They are moved into a Recently Deleted album (like the Trash on your Mac) and deleted automatically later. (They are kept for 40 days so it tales a long time for them to disappear)
Note in Photos.app this is not a normal album but accessible by File->Show Recently Deleted.
You can open the Recently Deleted album and delete itthe videos/photos from there to remove itthem from the device permanently. Make sure that you have a backup, because you can not undo this operation.