Okay, I know this is old hat for most here. But, I'm having the same issue of magically disappearing folders after power off/reboot of my LG Optimus Fuel. Also, I'm seeing Samsung here, though I have an LG. However, maybe this info can still help seeing that it's all Android.
I have found a workaround. But, know this, it is NOT a fix, but a very, very quick workaround that will help keep you from pulling out the remainder of your hair.
Okay, here's the dealio: Go ahead and set up your device exactly as you want it; and I mean set it up; put back all folders, shortcuts, widgets, etc. After you've done all that go to your "Home screen settings" (this name may vary/get there however your phone/device permits). Next, scroll down until you see something to the effect of "Home backup & restore" (again, name may vary/get there however your phone/device permits). Press on those words. A popup should appear to the effect of "Home backup & restore" underneath you should see "Backup" and "Restore". Go ahead and press "Backup". A confirmation dialogue should appear asking if you want to perform the backup. Go ahead and press "Yes". This should create a backup up of everything you just set up to your home screen (number of home screens do not matter, it's all backed up).
Now, whenever you need to shut off your phone, for whatever reason, you're free to do so. Yes, your folders will still likely disappear upon power up/reboot, however, now you can get everything back.
To get everything back follow the above procedure again, this time after pressing "Home backup & Restore", you're going to click on "Restore". You should get another confirmation popup asking if you want to perform the restore. Go ahead and press "Yes". All your hard work of setting up folders, shortcuts, etc. should be restored just as you originally had them.
As you add more folders/shortcuts/etc. just perform a new backup to keep it updated.
Well, I've tested this out twice in a row and it still works. So, I hope this info, or some variation thereof, helps somebody!
In Christ, for Christ