You are getting this error because you are trying to update your device over WIFI. NEVER update your device over wifi because it is too unstable. First, do a backup of your information in iTunes. Second, update your device in iTunes. If done this way you will never get the error stating you have too much data of your device.
To Backup Device in iTunes: iTunes: Back up your iTunes library by copying to an external hard ...
To update your device in iTunes: iOS: How to update your iPhone, iPad, or iPod touch - Support - Apple
This should resolve your issues