Relays are pretty basic, " a small current used to supply a larger current".
Has anyone fiddled with the wiring before or did this just start happening. Could be a short somewhere in the circuit, the larger power feed to the relay should be fused with a larger fuse than than the smaller current one. The "S" feed should not come directly from the key switch, to much current there for the switch,, it should go through a relay first.
If this is a "4" pin relay for the starter only, it should turn itself off after a start, therefore, it shouldn't overheat afterwards. If you could upload a diagram of that relay and the starter, it would also help. Does the relay burn out immediately or does it take time. Does the machine start well. The starter itself could be drawing too much current also, in that case, it would need to be replaced. This is only my quesstimate, it's hard to tell without being there. I've just re-read your post and see that this relay also supplies power to other components, were any of these working also at the time of overheating? One of them could also be the culprit.
