Not enough phone storage to install XAP
This article explains why the phone storage required to install a Windows Phone Application is significantly larger than the file size shown in the Windows Phone Store
Sometimes the Windows Phone store may refuse to install an application, even though the size of the the installation package (the XAP file) is significantly smaller than the remaining phone storage.
The reason for this is that the app size displayed on the Windows Phone Store is the size of the compressed application package (the amount of data that needs to be transferred over wifi or the cellular network to transfer the app to your phone). The app is much bigger when on the phone, and requires even more space during the installation process.
This article explains why this happens in more detail, and provides some ideas for how you can free up phone storage.
Why more storage is needed than the XAP file size
Before being deployed to the store, all the files of an application are zipped together and compressed, resulting into one file: a XAP package. The compression used by Windows Phone is really the well known zip compression format. If the package is to be deployed to a phone over cellular data, the file size of the XAP package is the amount of data that will be transferred to your device.
When installing the application, the phone first decrypts the XAP package (Windows Phone 8 only), does some checksum checks, reads the application manifest, and finally un-compresses the XAP package into phone storage. The decompressed data will occupy significantly more space than the original size of the file downloaded. And while installing, the compressed file lives side by side with the installed game, which adds up to the phone storage required during the installation. The compressed file is deleted once the installation is complete.
When a user tries to install an application using the Windows Phone store, the store will try to estimate how much storage will be needed by the application before the file is deployed to the phone. If the device doesn't have enough phone storage left, the store will not attempt to install the application. Note that the store estimation can sometime be well in excess of the actual needs.
After the installation, the application may also download some extra data (player stats, avatars, new levels) and use some memory for its internal operations: these will use extra phone storage on top of the storage used by the installation.
Note: It is the responsibility of the developer to delete the files he stores in the Isolated storage when those are not needed. The OS will not limit the amount of phone storage used by the application. If your app fails to clean up it may end-up using all the phone storage available on the device.
How to free phone storage memory
There are a number of approaches for freeing the internal memory of the device, ranging from deleting videos and apps, through to triggering OS internal cleanup. These mechanisms are covered in the article: How to free storage memory on Windows Phone