Hi,
After some investigations on my phone due to the same problem, I worked out what was going on. At least, on my S3mini.
1.- Go to Settings > Application manager
2.- Tap and drag to see all the applications installed. Sort them by size.
3.- Check the size of the biggest applications... and reckon if those sizes are consistent with the target of the application.
In my particular case, the "Contacts Storage" application had a size of 2.5GB!!!! So:
1.- I backed up my contacts exporting them to the SD card (.vfc file)
2.- I tapped on the application and I cleared the data stored (tap on "Clear data" option")
3.- I restored my contacts from the .vcf file
I hope it helps you out.
What I'm wondering is... how could a 6MB application reach a size of 2.5GB? What was stored in the file? I regreted I deleted it without checking it out previously...
Cheers!