Read @73's de Edd
reply. You need to add a snubber across the relay contacts, or install a new relay, hopefully with better contacts.
An RC snubber is a series-connected resistor and capacitor, placed across normally-open circuit contacts that are closed when you deliver power to the load... a fan motor in your instance. If is only effective with inductive loads (such as fan motors), that store electrical energy in a magnetic field and then release it, rather suddenly, as a current surge when electrical power is removed, i.e., when the circuit contacts open. It is this surge in current as the contacts are opening
that cause the arc that eventually damages the relay contacts. You can either eliminate the arcing, use better relay contacts, or do both.
In an RC snubber, the capacitor quickly charges through the low-valued resistor to whatever voltage is developed across the now open contacts to absorb the energy stored in the collapsing magnetic field. The capacitor then releases the energy more slowly through the series snubber resistor and the fan motor winding, thus avoiding the intense arcing that would otherwise occur.
You can look up snubber component values to use in online tables, or try a trial-and-error solution. I would start with an 0.1 microfarad, 600 WVAC plastic film capacitor and a ten ohm, five-watt, metal film resistor. If you can temporarily remove the relay cover to observe any arcing that occurs, it should be easy to adjust the values of the snubber components to eliminate any arcing you see occurring. Good luck with that. You can also substitute a relay with better, heavy-duty, contacts as Edd suggested... assuming you have space available and permission to modify the equipment.