It was so frustrating. My two year old 64GB iPad 4 running iOS 8 was constantly flashing ‘storage nearly full’ warnings. I couldn’t understand why: the first generation 64GB iPad it replaced always had around 50% capacity free. What was going on?
Today, I bit the bullet and did a reset to factory settings (Settings/General/Erase all content and settings) after doing a back up. As a result, I now have 31.5GB free space. It appears that the device is storing data from multiple back ups. Either way, I now have a working iPad again.