For anyone else that comes across this issue, it still happens till this day. My iPhone 11 was reporting 40 GB usage for com.apple.VoiceMemos
(even when I deleted the Voice Memos app) so I decided to backup my phone and restore to see if it fixes it.
Anyways I got the same error message as it turns out, 125 GB backup for 128 GB phone was still too much so I had to go through my iPhone backup (backed up with iTunes) with iTunes-Backup-Explorer and delete quite a lot of photos from the backup, maybe you can also use iMazing too. Point being, make a lot of space until iTunes actually begins restoring.
NOTE: please make a copy of your original backup before doing any modifications to your backup folder.