120 0utput port

If your solenoids are small (<150mA), then you could use the TPIC6B595 (ebay).
This chip is the same as a 74HC595, but with buildin mosfets.

Why a Mega. 15 shift registers only use three Arduino pins.
Leo..