Basic possible fix to see if this helps as when you say you have deleted everything accept the cache as well and that is most often the problem.
To clear the cache open settings then Storage and tap on cached data and in the next screen choose to delete. This is just junk files and no personal data is deleted doing this.
I would also delete cache partition from in recovery this often fixes bugs in the Android system such as telling you the storage is full it also often improves performance so worth doing and again no personal data is deleted doing this
To wipe the cache partition we need to boot into recovery
With the phone turned off hold the home key and the volume up key then turn the phone on keeping those two pressed. This is the most common method used by manufacturers to boot into recovery but without knowing what phone you have I can not tell you if this is the right way for your device. If that is not working for you use this link to find the method for your phone all phones running Android will have a method to boot to recovery.
When you have booted into recovery use the volume keys to move down the menu to Delete Cache Partition and press the power key to select it and follow the prompts it only takes a few seconds then reboot the phone the reboot can take a little longer than normal. I hope this helps.