The mistake is in categorising life as uncountable. While life on its own is often uncountable, here it's only part of the noun, and it's being used to mean capacity. The full noun is battery life, which is countable. A unit like a phone only has a single battery capacity or battery life, so the determiner a is appropriate.
Much here is intensifying longer, and longer is modifying battery life.
So the structure is "My new phone has a ". If we build it word by word, we get:
My new phone has a battery
The phone has a single battery; the determiner a is therefore appropriate.
My new phone has a battery life
Again - the phone has only one battery, and the battery has a specified capacity.
My new phone has a longer battery life
We add in the modifier that shows the battery capacity of this phone is greater than an older model. Now we finish with
My new phone has a much longer battery life
This indicates that the battery capacity of the new phone is a lot greater than an older model.