Apple unfortunately has made it difficult & confusing when it comes to ascertaining storage. Some of it is due to how the APFS file system works, but part of it is how Apple has macOS displays the information. So many times the information is incorrect or even outright misleading.
First thing to note is from your screenshots, you have only about 58GB of Free storage immediately accessible for new data. Unfortunately macOS tends to focus on "Available" storage which consists of actual Free space immediate available for use and "Purgeable" storage which is storage which at some unknown point in the future will be usable for new data. Only Disk Utility actually shows the Free storage value on its own.
Now to why you have 772GB of "Purgeable" storage. The data you deleted is most likely still being retained within one or more hidden APFS snapshots most likely related to Time Machine backups or a third party backup app. These APFS snapshots will be automatically deleted at some point once the backup has been completely transferred to external media. Some backup apps may actually keep an APFS snapshot for longer, so make sure to check the backup app's settings/preferences.
You can view and even delete APFS snapshots using Disk Utility. See this Apple article for details:
View APFS snapshots in Disk Utility on Mac - Apple Support
Be careful deleting backup snapshots before the contents are fully transferred to external media.
Another area where APFS storage becomes confusing is when you copy a file/folder to another location within the same APFS volume. The data is not copied, but a new link to the original data. In order to actually get free space back, you would need to delete both links.....when deleting the last link to the "copied" data, then the file system will finally delete the actual data which will provide more free useable space depending on whether an APFS snapshot still exists prior to deleting the data.
Hope this helps to explain things a bit. I hope I presented it in a way that makes sense since it is a bit confusing and I have never been able to find any online references which can provide this information in simple terms with diagrams & examples (those sites that do usually end up having other information or references which I feel can cause more confusion & problems for the average user).