74HC595 output voltage

If you weren't using protection diodes across the relay coils you will likely have damaged the 595 already... You don't mention if you had diodes.