iOS available space doesn't add up
Is this device older than 2 years and has never been reset? 

I can't tell you exactly what to do but this article quotes some possible solutions:


Do you happen to send and receive a lot of messages with multimedia? that could be clogging up some of your storage especially if you set the settings to delete messages to never.
How much space do you seen take by the Other category? Other may include:


  If you've ever connected your iPhone to iTunes, you're well aware of the "other" stuff taking up space on your device. This data contains things like Safari's browser cache, your email, Siri's cache, reminders, notes, stocks, weather data, emails (including attachments), text messages, iMessages (including images and videos), app data, etc.



Check voicemails?
Try to reset Safari Cache and data.



EDIT: OP indicated that the issue is indeed with the "Other" category, this article has some tips on how to try and locate and free up space taken by various elements that make up this category.Also check this Apple forums thread. Download any mentioned software there after doing your own DD.

Here's what "Other" includes, in full:


  Browser cache
  
  Mail cache
  
  Mail messages
  
  Mail attachments
  
  Safari's Reading List
  
  iTunes Backups
  
  Crud resulting from jailbreaking your iDevice
  
  Game data
  
  Saved data files
  
  Call history
  
  Notes
  
  Media
  
  Voice memos