LM2596 buck converter overheats converting 36DC -> 5DC at 600mA

These converters are often advertised on eBay as working up to 40V and 3A with 92% efficiency. Don't believe it.

The 'LM2596' may be a fake. But even if it's a 'good' fake, what kind of performance can you expect? I simulated the LM2596 in TI's WEBENCH®. Here's the circuit...

And here's the simulation result...

Only 74% efficiency at 600mA! That equates to 1W of power loss, which could make a small board quite hot. However in the simulation the inductor only dissipated 0.16W, much less than the LM2596's 0.54W. Your inductor is getting hotter than the IC, which suggests it may have higher resistance and/or magnetic core loss than the simulated component.

The combination of low inductance, high voltage drop and low current results in high ripple. A circuit designed for low output current might achieve higher efficiency by using a larger inductance value, but then it would be worse at high current. I am guessing the original designers of this converter wanted to get the greatest current and voltage range they could out of it, so they used the minimum inductance value they could get away with. Then someone else copied the circuit, but substituted the inductor for a physically smaller part with higher resistance and lower saturation current. And if the LM2596 is a fake...

Is it reasonable to chain the converters, like using the first buck to drop something like 36 -> 20, and then the next one to drop 20 -> 5?

Yes, this should help. Efficiency improves at lower voltage drop, so you could try cascading converters (eg. first from 36V down to 12V, then from 12V to 5V) so the voltage differential that each one has to handle is reduced. Total efficiency may be worse, but each individual converter is more efficient so they should run cooler.

The inductor getting hot probably indicates it is undersized for the relatively high input voltage you are feeding it.

Suggest trying substituting a larger value inductor from a reliable supplier. It is probably saturating. Saturation will also cause the LM2596 to heat up. You could also pull one or two inductors off the ones you burned out and connect them in series with the existing one.

If inductor saturation is the problem, converting in two stages may not be of any help. I suspect it's the high input voltage with a relatively small value inductor that is better suited to a 12V input.

The LM2596 is certainly fake (a real recently purchased one would say TI on it), but may still be okay.

You say that input voltage is 36V, current 140mA, output voltage 5V and current 600mA. So, input power is 5.04W, output power is 3.0W. Efficiency ~60%. (That conforms to datasheet graphs)

This is efficiency for 3A load. I can't find efficiency for lower loads, but efficiency is usually lower for currents lower than rated current.

You dissipate 2W.

There is almost no heatsinking, so you can't be surprised that it gets very hot. That is just poorly designed and/or not very suitable for your application.