My answer to this is that software engineering is a lot more like creating a blueprint than creating an artifact based on that blueprint. Or put another way, it's usually more of a
design process than a
manufacturing process. (I've switched analogies on you, but "painting walls" in your analogy is akin to "manufacturing artifacts" in mine.)
The "manufacturing the artifact" step in software is done automatically by the computer, when given the "blueprint" (code).
I guess to try to go back to your painting walls analogy. In my view, creating software is more like if someone asked you to create a wall-painting machine that will work for any room that fits a certain specification. They could contract you to paint just one room in this way, but that would certainly be harder than just painting the room! But more likely, they have a million rooms they want you to paint. Either way, the hard part is creating the room-painting machine. And it would indeed be quite difficult to give an accurate estimate of how long it will take to do that. But once that exists, you can easily estimate how long it will take to paint any individual room.
And real engineers, indeed, have this same issue with the design phase of projects, for the same reasons. Just like us, they try to break apart and estimate how long it will take to do that part, but just like us, my impression is that it is known to be fraught to accurately estimate that part of a project.
But also just like us, this is a continuum based on how novel the thing they are engineering is to them. On the one end of the spectrum, there is the equivalent of off-the-shelf software, like using a blueprint for a standard single-family home that's been built a million times already. And on the other end of the spectrum are things like designing the motor for the first model of a new electric vehicle manufacturer, where it's all brand new. But then there's a whole spectrum between those two, where it is fairly easy to break down and estimate the design process for things you've done a bunch of times, and nearly impossible for things you've never done.
This is a very long-winded way of saying that the difference comes down to how novel the project you're working on is! This is why freelance / contractor shops do best when they find a particular niche of a kind of thing to build, and then find clients who want them to build essentially the same thing over and over again. It really is possible to get very good at estimating this kind of nearly-cookie-cutter work. (I did this a bit for awhile back in the day, with multi-page Rails CRUD apps, and it was indeed easy to break things up and estimate.) But this is also why it can be frustrating to work with freelance / contract shops, because it behooves them to figure out how to fit your project into their cookie cutter, and that can end up being a worse outcome than building something bespoke, iteratively, without a detailed plan and estimate.