OK. I'm going to guess that there is enough power (Watts) to the starter when the solenoid is directly connected to the battery. And not enough juice getting through when going the relay.
So the question is why?
Some possibilities:
Weak battery?
Restriction in the circuit to the solenoid?
Starter failing and demanding more power?