If the relay is clicking, try out a replacement but it could be the temperature sensor on the back of the radiator. I'd clean up the contacts on that too.
If either are knacked, then they're both small, wallet-friendly parts, though sometimes the temperature sensor gets so seized in that when you try to unscrew it, it wrenches the radiator casing (new rad' time).
The chronic fuel consuption is probably unrelated as the relay and temp. sensor just relate to engine cooling. I reckon that your thermostat is coincidentally sticking, so your car is taking longer to warm up (and is running richer all the while). It should warm up (to "Normal" on the temp gauge within about 7 minutes).
A new thermostat is £15 or so, and dead simple to change.