Cannot transfer backup to a new iPhone 12 Pro. Not enough space error

Around 6 hours spent in vain. The backup for iPhone does not work. Apple is useless. Cannot make their software work!

My old phone is iPhone XS Max with 256 Gb. I've been deleting data to keep in under 128 GB (which my new iPhone 12 Pro has), then I lowered the bar to 110 GB, then to 100 GB, eventually to 80 GB. Each time I spent a lot of my time to find data to delete. Nothing worked! There is no way I can transfer my data to my new phone.

I spent much of my time repeating "transfer your data" from iPhone to the new iPhone process directly from the phone. Each time the same error after minutes of trying "not enough space to transfer data". Why not enough space if iPhone Storage usage shows 80 GB and the new iPhone has 128GB???

Funny part, then I called Apple. They advised backing up via the computer. Firstly, I couldn't find space on my Mac. It has 170 GB free, but complained "not enough space" to back up iPhone. Then I switched to PC with extra space. There I managed to create a backup which was roughly 170 GB!!! (while showing "using 80 GB on the device"). Of course, it didn't work for my new iPhone 12 Pro.

Then I decided to remove all Photos. My guess was that iCloud photo library might be the cause. Yes "Optimize storage" was selected, without it all my Photos would lots of space. I turned off iCloud and checked "remove photos from device". It seems that major number of photos remained on the phone. Actually, used space increased to 170 GB. All other checkboxes for Photos/iCloud didn't make any difference in terms of storage usage (General/iPhone Storage).

Called Apple again, they asked the same questions again and again. Finally, advised me to turn on iCloud for photos, wait till the sync finishes, then try backing up again. The process shows still 1% (after a couple of hours).

While waiting I tried to restore from the backup I created earlier today on the same old iPhone XS Max 256 GB. The backup didn't work for the same device!!! I cannot restore from a backup created from the same device! That's nonsense.

It is great, you, Apple, can make nice animations and art, even turn on nice music while waiting for the support specialist, but you totally useless with the real stuff, the software your devices use. It does not work.

The only option I have for now is to start the device as "new iPhone" which will add me some pain to set everything up. And, I will lose some data which is not in iCloud. request 101221201737