For others that may reach here with similar issue for recent Joomla updates (e.g. 3.6.5).
In the case you get this error message, it usually means what it says: That the update package that was transferred to your Joomla instance's tmp folder is indeed corrupted. A corrupted file may occur for various reasons - no need to analyze this here.
If this happens, any new effort to initiate the update procedure through the Joomla Update Component will end with the same result - as Joomla will keep finding the corrupted zip file in the tmp
folder and will try to use this for the update.
So the solution here is to connect with FTP to your site and go into the tmp
folder of your Joomla and delete the previous downloaded update package. This will force the Joomla Update Component to fetch and download a new zip archive for updating your Joomla site - hopefully this time the archive will be transferred at full and with no corruption.