This is a chronic problem with my Windows Phone. The only solution I have found, is to backup everything, especially verifying if your photos from the phone, actually did backup to OneDrive. Check every photo, compare the photos on the phone with those on the OneDrive web site. Re-Sync those on your phone, that didn't get uploaded to OneDrive. Then, check and compare again. Do it again, if the photos are important and you don't want them lost forever.
Then hard reset/reboot your phone. Reinstall/log in to all your apps and set them up as you had previously.
The gigabytes of unknown wasted "Other" will be gone and you can start to enjoy your phone again. For me, it eventually, builds up again. Rinse and Repeat.
Best Wishes.