I got an error today trying to install a patch. It does still take up space. I found it via ftp under /user/download
Edit: but even after deleting it, it doesnt seem like PS4 knows its gone (even after a reboot), probably have to do some sort of database rebuild for that to be recognized. But as far as I know a rebuild will wipe all fake pkgs (SO DONT DO THAT).
A workaround I found was to delete the game the update was for.
So step by step:
1) Had Horizon installed (working fine)
2) Tried installing update, update failed and still took up space (shows up under Other in Storage at the very bottom of the list)
3) Deleting Horizon deleted both the failed patch and the game
4) Reinstalled Horizon
Shitty workaround but it worked. If anyone finds a better way please let us know.