Your problem isn't the storage, it's whatever you are doing locally that is the issue. I've got tens of thousands of files backed up with no issues, across several devices.
You didn't mention your OS. I'll assume you are running Linux because if you are running WIndows/MacOS you are missing a fundamental weakness already.
On Linux, use EncFS which also has a nice GUI manager via GEncfsM for those that prefer it.
Using EncFS means you don't have to upload entire files when you edit them, only the changes are synced. This is efficient, open-source, and works perfectly.
Once EncFS is working, pick any cloud storage you want and sync the encrypted folder(s). I do it with Dropbox + symlinks and it is flawless, no issues for years now.
As long as we're going to reinvent the wheel again, we might as well try making it round this time. - Mike Dennison