Heat buildup like that is due to high resistance in the fuel pump circuit. Sometimes a worn fuel pump will draw more current than a newer one as well, which can also contribute to the overheat. But, a good circuit should be easily capable of supplying the few extra amps that a worn fuel pump will draw.

Typically, the high resistance is at a connection. The relay terminals connect to female terminals. The male terminals of the relay (spade type) are designed to fit tightly into the female terminals. If they fit loosely because the female terminal has spread open too far to grip tightly, the connection will build heat. Also, oxidation of the metal terminals' surface can cause extra resistance. That is why it is recommended to check each female terminal by inserting a single male terminal to judge the tightness of the fit. If the fit is tight, the metal scrapes against it's mating surface when connected, cleaning away any oxidation where the metals contact each other. Water and oxygen can degrade even a tight connection. The use of silicone dielectric grease on the terminals before inserting the relay will help protect the metal from oxidation and corrosion, to extend the life of the connection and prevent the buildup of resistance.

If a used fuseblock is installed, check the terminal fit before installing the new relay. Use the dielectric grease once the terminals are checked. Replace any terminals that are badly corroded. If the terminal fit is loose, most techs will release the terminal from the fuse block by using a pick to depress the terminal's locking tab. Then the terminal can be pulled out and serviced individually. A slight squeeze of the female terminal with pliers is usually sufficient to make the female grip the male terminal tighter.

Once all the terminals are verified to be good, install the relay, and run the vehicle, check the relay to verify it is not getting too hot.

Technically it is possible to have a problem inside a relay that causes heat to build up, but it is not as likely as a bad connection since the relay switch has a contact as well. Inside the relay is well protected from the elements, and does not depend on a male female type connection. So I think the most likely root cause was one of the terminals building up heat from a bad connection. The heat damage may have made it impossible to determine exactly which terminal was at fault. I would carefully inspect the two terminals of the relay (numbered 30 and 87) that carry power to the relay, and from the relay to the fuel pump. One of these terminals in the fusebox may have had a poor contact due to loose fit onto the male terminal of the original relay. Try cutting off one of the male terminals on the burnt relay (30 or 87), and test fit them into the old socket for the relay, to see if they were fitting loosely, as a way to identify what caused the problem.

The day before the no-start, it probably was melting while driving, and upon cooling, it may have oxidized even more and resulted in the no-start. If you are not electrically inclined, you can still replace the damaged components and have a technician perform voltage checks to verify the relay is connected well, and that the fuel pump is getting good voltage. At the fuel pump, connecting a voltmeter across the two wires will tell you whether the pump is getting full battery voltage. If the voltage is less than battery voltage by more than .5 volts, there is unacceptable voltage drop somewhere in the circuit. The voltage drop forces the current to increase in order for the pump to receive the same power. The current flow is a critical factor in heat buildup. The wiring from the pump to ground (where a wire connects to the frame or body metal), and between the pump and relay should be checked to make sure no other issues exist.

Basically, the relay connection acted as a restriction to current flow, building up excessive heat. In a proper working system, the relay acts as a simple switch to pass the current to the fuel pump. The relay should not cause any resistance
to current flow in a proper system.

Most likely, replacing the fuse block and relay will resolve the issue, but the overall circuit should be checked for safety's sake.