I saw many people asking on other websites why they have cleared all thier photos and videos but the iPhone still keeps telling them "iPhone storage full"... Since iOS 8, the pics and videos you deleted are not actually gone. If you want to make them disappeared forever you need to go to the "Recently deleted" album and delete them again... Otherwise you need to wait for 30 days they will be deleted automatically