Allright fellas, here is the SOLUTION you've all been waiting for until Apple releases a fix for this most disturbing bug.
Also I should mention that the solution before me unfortunately didn't work for me on iOS 8.1. I wanted to mention that if anyone else is trying to go with that and having no luck.
Anyways, for this solution to work, you'll need a computer(either a Mac or PC) and a computer app called iExplorer(http://www.macroplant.com/iexplorer/ - it's 35$). Basically, iExplorer allows you to browse the file system of your iOS device through a USB connection from your computer without jailbreaking it.
BACK UP your iDevice!!! DO NOT proceed without backing up your device since this method involves some risk but rest assured I'll direct you as best I can. Also you should know that any problems that may occur are totally at your own responsibility.
I'm assuming you've installed iExplorer into your computer and your iOS device is connected via USB.
1) Start iExplorer,
2) Select the 'Files' tab,
3) Select the 'Media' button:
- if a pop-up appears about telling you that it's dangerous going to this location, then accept it. you should be going there if you want to fix your storage problem
- although the pop-up is correct and it should not be underestimated. you'll be dealing with the file system of iOS(at least a part of it) which a wrong deletion might lead to problems BUT if that happens, as always, a good old restore should fix everything magically.
4) I found those problematic videos scattered under two different locations:
- a very small part of them was under: my 'iOS device > Media > Downloads'. At this location, you'll see a lot of folders with bunch of numbers on them. You can check them out for videos BUT the second location had most of the problematic videos anyway. Also you should know that folder sizes won't be visible until you go inside them and back out.
- the second location was 'iOS device > Media > CloudAssets'. At this locations, select the header of the 'Size' column in order to list the items in a descending order so that videos would probably be at the top assuming that videos are the most storage hungry things on your iOS device. Video files will have the '.m4v' extension. One quirk of iExplorer is that unfortunately it can't delete multiple files at once that you'll need to delete them one by one. Video files will have some '.plist' extension files(which are really really small files) as well but these are basically files that store some information about the video files that are safe to leave behind.
That's it. When you delete the video files, your storage will immediately increase.
You should also know that I recently filed a bug report with Apple about this problem and they told me that they are aware of this issue and other people have reported it as well.
Take care 😉