Exactly the same issue here.
APFS apparently "forgot" about some snapshots (tmutil listLocalSnapshotDates returned no snapshots)
it was a pain to get fsck to work correctly
- for anyone needing it, the only way to fsck the APFS container is to boot in Safe Mode (CMD+S) and run fsck_apfs -y /dev/diskXsY
- if you first run fsck_apfs -n or something else, it will fail saying it's mounted writeable (not true), and the same error is returned in Recovery mode
fsck "corrected" the number of snapshots (3->0), but still no space was freed
now similiar messages can be seen in dmesg when I "delete" something:
apfs_update_phys_range:2459: Attempted to dereference range 23977274+520 but it isn't entirely there! (found gap at 23977274, next range at 23977794+32)
apfs_update_phys_range:2459: Attempted to dereference range 23978154+508 but it isn't entirely there! (found gap at 23978154, next range at 23979193+1)
apfs_update_phys_range:2459: Attempted to dereference range 23978928+246 but it isn't entirely there! (found gap at 23978928, next range at 23979193+1)
apfs_update_phys_range:2459: Attempted to dereference range 23979315+1030 but it isn't entirely there! (found gap at 23979315, next range at 23981118+5)
apfs_update_phys_range:2459: Attempted to dereference range 23980619+467 but it isn't entirely there! (found gap at 23980619, next range at 23981118+5)
While I'm still hoping the system would "fix itself", I wouldn't bet on it, and the correct way to resolve it is to restore from backup.
Btw backups stop working because APFS refuses to create new snapshots with "out of disk space" message - not sure if that's a side effect of it being b0rked, or whether it needs/wants more free space to be safe.
P.S. while the free space is constantly decreasing as time goes on, sometimes a few MBs are freed, so maybe not all hope is lost...