In order to drive the prop, the turbine stages of a turbo prop are specifically designed to extract as much energy as possible from the “jet” before it goes to atmosphere. Thus there is considerably less wasted energy in its exhaust compared to a jet. Hence less fuel flow for a given amount of power.
As you say, the turbo prop blows some of this advantage if you go too high as the prop efficiency degrades up there.