Why is the Tu-95 so efficient despite having propellers that spin faster than the speed of sound?
Yes, propellers have problems at high speed, but if done right, they still have an advantage over turbofans at speeds up to Mach 0.8. Look at the inner engine gondolas of the Tu-95: They are elongated and thicker aft of the trailing edge. This was done to stow the landing gear in them, but also to area-rule the aircraft. The Tu-95 applies knowledge that was gained only in the early jet age. This, of course, also explains the swept wing.

Next, it uses contra-rotating propellers which spin very slowly (just 750 RPM). By having two coaxial propellers spinning in opposite direction, the efficiency at high speed is improved. The first propeller pre-swirls the flow so the flow conditions on the second propeller are more favorable for thrust creation.

The tips of the fan blades of a modern turbofan also move at supersonic speed, so the supersonic propellers on the Tu-95 do not create a direct disadvantage. By keeping the relative thickness of the blade near the tip low, the drag increase can be kept at tolerable levels. But make no mistake: Supersonic flow adds wave drag, and especially around Mach 1 the zero-lift drag coefficient of everything which moves through air has a maximum. It would make the Tu-95 even more efficient if it would fly at a lower cruise speed where the propeller tips are still subsonic, but Tupolev wanted to push the design to the highest useable cruise Mach number.

What you learned about propellers and jets is not wrong, but it is not a black and white world, either. Airliners use jet engines to fly at the highest cruise speed possible, but at the cost of higher fuel consumption. If they would restrict themselves to lower speeds, plenty of fuel could be saved. But too few people would book these flights, because on intercontinental routes they will take noticeably longer. Note that turboprops are still used in regional air traffic, and even the regional jets have lower flight speeds than the intercontinental jets.

Now to the efficiencies of engine types:


Piston engines are the most fuel efficient aviation engines. Their drawback is a constant power output over speed, so that thrust is inverse to speed. This helps for acceleration at take-off, but limits maximum speed. A modern piston engine uses 240 g of fuel for providing 1 kW of power over one hour: 240 g/kW-h. Diesel engines use as little as 220 g/kW-h. This number is already true for the old Jumo 205, among the first aviation diesel engines in operation 80 years ago.
Turboprop engines are next, and their power increases a little over speed due to ram pressure (which will raise the internal pressure in the engine by approx. 30% at Mach 0.8). Their power-specific consumption is about 300 g/kW-h but goes down with increasing size, so the biggest turboprops approach piston engine levels of efficiency.
Jet engines are less efficient than both, but are better for flying fast and high. Their thrust drops even less with speed, so the better basis for expressing consumption is thrust, not power. The typical fuel consumption of a modern jet engine (GE-90) is 30 grams of fuel per Newton of thrust over one hour (30 g/N-h) when run stationary, and twice that in cruise at Mach 0.85. Modern Military jet engines achieve 80 g/N-h at take-off and have roughly constant thrust and specific consumption over speed. Since most innovation happens on turbofans these days, the most modern turbofans again approach piston engine levels of efficiency, but if you compare the same technological standard, they are less efficient than their piston and turboprop contemporaries.


In all cases, thrust is created by accelerating a mass of air backwards. The general equation for propulsive efficiency $\eta$ is $$\eta = \frac{v_{\infty}}{v_{\infty}+\frac{\Delta V}{2}},$$ where $\Delta v$ is the speed increase of the mass of air due to that acceleration. This formula shows that it is better to accelerate a big mass of air only a little than a smaller mass by a lot. Propellers do this and for that reason offer the best efficiency. Turboprops use less efficient, but lighter gas turbines for creating power, but retain the efficient propeller. Civilian turbofans try to increase the mass of air by increasing their bypass ratio, and only the military is using the least efficient types with bypass ratios below 1, because they are the best choice at supersonic speed.

Below you see a plot of the thrust-specific fuel consumption in cruise condition of different engine types over their bypass ratio. The inverse relation is easily visible.



Plot of the thrust specific fuel consumption in lb of fuel per lb of thrust per hour of different engines over the logarithm of their bypass ratio (picture source).

To make a comparison between piston and turbofan engines possible, let's compare fuel consumption at take-off. The formula for static thrust of a propeller is $$T_0 = \sqrt[3]{P^2\cdot\eta_{Prop}^2\cdot\pi\cdot d_P^2\cdot\rho},$$ where $P$ is the shaft power, $d_p$ the propeller diameter and $\rho$ the air density. For our example, we use a four-bladed prop of 3.4 m diameter and an engine with 1111 kW power. Its static thrust is 10.727 kN when we assume standard atmospheric conditions and a prop efficiency of 85%. The fuel flow will be 266.6 kg per hour, and relative to thrust this is 24.8 g/N-h or just 80% of that of a modern turbofan. 

I wonder if even the enthusiasts could guess what airplane I used, because I obfuscated it by using those unfamiliar metric units. I guess nobody will argue that it is not optimized for fast flight, so this comparison should also hold for the Tu-95, for which I have less data available.



Here follows the requested expansion on propeller tip speeds. Thanks to the excellent comment by @JanHudec not much is left to say: The propeller diameter is 5.6 m and their speed is 750 RPM, so the circumferential component is $5.6 \cdot \pi \cdot 750 / 60 = 220 m/s$. Add to this the cruise speed of Mach&nbsp;0.67 (taken from this site &mdash; others list quite incredible numbers) at altitude, where the speed of sound is 295&nbsp;m/s. Mach&nbsp;0.67 equates there to 197.65&nbsp;m/s, and vector addition gives 295&nbsp;m/s for the propeller tips, exactly Mach&nbsp;1.0. This means that the propeller is subsonic over its whole span.

But the top speed is quite a bit higher. Thanks to the excellent work of Ferdinand Brandner and his team back in the Fifties the NK-12 engines developed already 12,000 horsepower back then, and their power output has since been raised to 14,795&nbsp;HP. This allows a top speed of Mach 0.82, and now the tip speed comes out at 327&nbsp;m/s or Mach&nbsp;1.08 &mdash; mildly supersonic. This means that the outer 30% of the propeller experience supersonic flow.

I fail to find a source for the range figures you list in your question. Again I refer to this site: It is 7,800 miles or 12,552&nbsp;km at a cruise speed of 400&nbsp;knots or 179&nbsp;m/s which equals Mach&nbsp;0.606 at altitude, resulting in Mach 0.96 for the propeller tips. Therefore, it seems the best range is reached with subsonic propeller tips.