Of this I was aware.
The Merlin doesn't have to be the 1650-3. The V-1650-1 could give a useful altitude performance gain without much weight penalty, and it shouldn't require the massive increase in cooling capacity for the -3.
Though Packard didn't make them, I wonder how a Merlin 45 would have gone in the P-39. Obviously low down performance would suffer, but there should be some gain at higher altitudes (the 45 having a higher FTH than the Allison).
Actually not by that much once the later Allisons with 9.60 gears showed up. Critical height the Merlin 45 may be 3-4,000ft higher than a late model P-39 which would be a help but not solve the problem. The Late Allisons sort of split the difference between an early Allison and the Merlin 45.
A big problem is the weight, A P-39D clean is about 1000lbs heavier than a Spit V clean or almost 15%. Put together with the smaller wing and the wing loading was about 30% higher. At altitude the P-39 has to fly faster just to keep from stalling leaving that much less power for climb and maneuver.
Then you have a take-off problem. Early P-39s had 1150hp for take-off, late model Ds, Ks and Ls had 1325hp for take-off and the late versions had 1200hp for take-off. Merlin 45 had 1230hp for take-off at 12 lb boost. While the Allison was rated for 5 minutes CLIMBING at take-off or Military Power the Merlin was not so rated, what they did in the squadrons I don't know. We do know that Allisons tolerated over-boost abuse fairly well at low altitudes.
Indeed, I was thinking about V-1650-1 (note to self - next time be direct, instead of being cryptic).
That engine was able to outperform single stage V-1710 at every altitude, and it was available earlier than the '9.60 V-1710s' show up. Installation of that engine would've dictated also the relocation of (now longer) engine intake into a place not hampered from having the canopy ahead itself, should help to better use of ram effect.
The main problem to get V-1650-1 in P-39 would've been the low availability; also, IIRC the reduction gear was integral with crankcase - not compatible with P-39 power-plant installation.
BTW, the grpah kindly posted by krieghund neatly describes the single-stage V-1710 as an 'altitude rated engine'