How to extends Arduino Mega to 250 I/O pin
You can definitely use the TPIC6A596 from Texas Instruments.

Its outputs are more than capable of driving your relays, to have 150 outputs you will need to daisy chain 19 of them.

The chip features an eight bit shift register, clocked by the SRCK pin. This shift register can then be loaded at once in the output register, so that the relays will always be driven.

To daisy chain the chips you will need to connect the SER OUT pin of the first chip to SER IN pin of the second, and so on. The last SER OUT can be left unconnected, while the first SER IN must be connected to the Arduino.

The SRCK, RCK, /SRCLR and /G pins can all be connected together and to other four outputs of the Arduino, so that you will need a total of five pins to drive your chain.

A pseudo routine to manage the whole thing follows:

At power up you want to keep both clock inputs low while resetting both the shift register and the output register tying /SRCLR low. It is probably a good idea to keep the output stage disabled too, keeping /G high.

Now that the chips are in a know state, release the reset and tie the enable high. All the relays are off and you are ready to clock in the first
152 bits.

To do so just start toggling the SRCK pin while putting data on the output pin of the Arduino. The data is sampled by the chips on the rising edge of the clock. For proper timing please refer to the datasheet, maximum clock frequency is 10MHz, a full shift requires about 15.2us.

When all the data is clocked in, stop toggling SRCK, keeping it low, and produce a single clock pulse on RCK: the output registers are simultaneously loaded with your data.

When you want to change something just clock in the new bits and only when you are finished strobe RCK: doing so you ensure that the relays status is known at any given time.

This is about it, but there are a couple of remarks:

You will need to add protection diodes to your relays. This site is full of examples about it so I won't dig into the issue.

The typical RdsON is \$1\Omega\$. Your relays are 50mA, eight of them adds up to 400mA, this is 400mW dissipated in the chip. Times 19 chips it adds up to 7.6W. This is quite some power, and your board design should take this in account. There are some thermal suggestions on the datasheet, please read them and understand the implications. Without a copper heatsink the thermal resistance is 80degC/W, at 0.4W that's 32degC above ambient temperature. Depending on your application this might be acceptable or not.

Maximum operating frequency is 10MHz, but I have got the feeling that you do not need to go this fast. Keep also in mind that you will be driving 19 inputs with a single Arduino output for the common pins. This is probably fine but the capacitive load can be quite high, so the rise and fall time will be long. I am not sure if this is an issue, this needs some measurements, but if you keep your clock slower you are safer and probably meet your timing specifications anyway.