They are air, oxygen really, constrained.
You are right that the electric motors themselves won't suffer from the same oxygen starvation, but as the other commenter noted, the props or impeller blades will. They need something to push, there isn't much up there.
I'm not sure how it has to do with electric propulsion, though - I'd think systems like NERVA is a more exciting solution in this kind of domain(jk).
Short haul passenger flights are not about speed but about getting directly to the stopover, without the unpredictability of ground transport. A "powered glider" with separating assist for the climbout could be a great match for that task.
And the tug would obviously not really be a tug, but a winged battery directly attached to the aircraft it supports, with barely enough wing for a controlled return. An electric drop tank. Not exactly unheard of in military aviation (except for the "electric", obviously)
Fighter aircraft are generally built for speed and have (even relative to commercial aviation) often fairly low range. The equivalent to "tugging" would be external jettisonable fuel tanks, and we have seen those in military use since at least WWII. Given the general lack of electric propulsion in military use, that seems reasonable. The other model has been JATO packs applied to both fighter and cargo aircraft (Fat Albert, a C-130 Hercules, is often fitted with these for air-show demos). Not electrical power, but an external boost assist.
For drone craft, there are deployment scenarios in which a large cargo plane drops (electrically-powered) drone swarms. I don't know the extent to which this has been deployed, but again it's similar.
If a military were to adopt tugs, I'd expect them to be applied to drone or cargo missions, either with a drone tug (similar to the cargo-plane model above, but possibly with remotely-piloted / autonomous tugs), or with some capability for lofting a battery pack that could be detached and flown back to the take-off site after contributing to initial take-off and climb. That is complicated, but might fit certain mission profiles, and for a relatively slow long-haul cargo mission might make the cut.
Worth also noting that most EV aviation concepts are for relatively modest cargoes and distances. The more viable range from 2--12 passengers for perhaps 100--200 km at low speeds. I've seen some more ambitious proposals, but they strike me as not especially viable.
Turnaround time for planes is short enough that you’d need to do a battery-swap rather than a battery-charge anyway.
A winged battery which could drop away at ~FL20--30 or so and return to either the origin field or some secondary collection point might be all you need, rather than tossing batteries out the cargo bay throughout the flight.
I also suspect that most EV aviation will be shorter haul such that a large set of drops wouldn't be necessary.
Without doing hard calculations, it intuitively feels pretty marginal potential flight weight savings for the operational complexity it would add
[1] https://aviation.stackexchange.com/questions/47262/how-much-...
Worth noting that EV aircraft flight segments are likely far shorter (100--500 km, maybe at a stretch 1,000 km, not the ~5,000 km of JFK->LAX), and cruise much slower (~100--300 knots, say), so climb-out would be a proportionately larger share of the energy budget.
And ditching 20% of your energy storage mass immediately on attaining altitude would still be a considerable savings for the remainder of the flight as that mass doesn't need to be kept aloft.
EV aviation (and aviation itself) is a battle of thin percentages. EV aviation itself has relied strongly on materials advances (advanced fibre composites), and reducing crew (ultimately: autonomous piloting). The need for cabin crew for safety reasons remains, and would be a significant hurdle. The extent to which non-revenue occupants and payload can be minimised likely plays a huge role in any eventual success. A 19% reduction is nothing to be sneezed at, if it can be achieved without significant other compromise.
Electric propellor planes have similar problems at high altitude that you're pushing thin air.
What are the efficiency gains you're thinking about?
In any case, electric engines don't need oxygen.
Coffin corner is a real thing.
Theory != Practice. If that were the only variable, then yes. Electric would be great. But it's not. It's far from the only thing in play. Lift also suffers from thinner air. Pure electric (as-in battery/solid state energy storage) could have 100% efficiency (specifically in converting prop/turbine torque to thrust of moving air), and it'd still have a terrible efficiency problem with current day tech.
Electric's primary efficiency and efficacy issue is regarding the total operating weight of the aircraft compounded by how that weight does not meaningfully decrease as the battery banks are depleted as compared to consumable fuels. Weight is your biggest enemy in flight, not power nor mechanical efficiency.
Hybrid electric (be it consumable fuel through a generator or fuel cells) is much more promising, but rarely what people mean when discussing "electric propulsion" (without the hybrid qualifier), and still has issues of it's own.
Not sure about electrifying engines for slower planes, that currently use turboprops. Would that be an electric prop too?