I had this issue and deleted almost every app, picture, or video but nothing helped until I actually went to My Files -> Android -> Data and selected all from that Data folder and deleted. I have had no issues with any of my apps and that out of space error is not showing anymore.
Note: I was...