I have the same problem!!!! PLEASE HELP!
First I would simply try clearing the cache in storage. Go to your settings, scroll down to storage and click, scroll to cache and click. When pop up asks delete? Click yes.
If that doesn't work, then you can try to wipe the cache partition. That's more involved but it won't wipe your phone like a factory reset will.
To wipe cache partition, turn your phone off. Then hold down volume up and home button and then power button. When the screen comes up release the power button, but continue holding home and volume up until the recovery screen appears. There you will see an option to wipe cache partition. Choose it with power button. Then wait... It can take a few minutes to 25 of 30 minutes to complete.
Wiping cache partition is involved, but it doesn't wipe everything from your phone like a factory reset does and it fixes a multitude of problems.
(and thanks again to Lucianus_Luciferius for helping me find cache partition wipe on the S6)