How to Clear Space from your Mobile Device, and What to Clear:

Removal of Data from a Mobile Device:

Troubleshooting iPhone Storage:

Internal storage cannot be upgraded. It is what it is. So, the maximum internal storage capacity never increases, even if you upgraded your iCloud plan. Learn More here: What's the Difference Between Device Storage and iCloud Storage? Apple Support. 

So, what to clear...

Clear Internal Storage:

Try clearing internal storage though use of the following:

A. Clear Temporary Internet Files:

-- Cookies perform remembrance of certain site-entered data.

-- Caches keep a snapshot of the last time you visited a site.

-- Go here: Clear the History and Cookies from Safari on your iPhone, iPad, or iPod Touch - Apple Support

-- Do the same for all other Web browsers. View the Help menu for info on how to do so.

And...

B. Clean TV and Music Libraries:

Remove all unneeded files from your TV and Music libraries. Full-movies take up 2-4GB typically, and a bunch of those would take up a load of storage, ideally. So, if you have any movies that are not needed, then delete them.

And...

C. "Other" being the Culprit:

Use my User Tip: The storage named "Other"( Now Called "System Data") is the grey bar that is seen in Storage. Sometimes, it can unknowingly take up GBs, and TBs of storage. So, look into clearing that as well. See my User Tip for More: How to Clear "Other" in your iPhone's Storage - Use Backup - User Tip