On a Uno, all of the digital and analog pins can trigger a pin-change interrupt. That gives you 20 inputs straight away. The Mega also has pin change interrupts but not on all its pins. The pins that the Mega supports for pin-change interrupts are documented on the Software Serial page.
Not all pins on the Arduino Mega and Arduino Mega 2560 support change interrupts, so only the following can be used for RX: 10, 11, 12, 13, 14, 15, 50, 51, 52, 53, A8 (62), A9 (63), A10 (64), A11 (65), A12 (66), A13 (67), A14 (68), A15 (69).
(Note that the Atmega2560 chip itself supports more pin change interrupts, however those extra ones are not brought out to header pins on the Arduino board).
That's still quite a few (18 if I counted correctly). Plus the hardware interrupt pins: 2, 3, 18, 19, 20, 21.
Right now I'm using 4, but i want to reach up to 60 sensors, and a minimum of 16
To reach 60 you probably want an input shift register such as the 74HC165 - you can daisy-chain them together to get lots of inputs. However you would have to poll to see if pins changed.
Otherwise you could use something like the MCP23017 chip, which has 16 input/output pins, and supports interrupts. You can use 4 of them (interfacing with I2C) and thus get 64 inputs. There is a shield that has 4 of those chips on it:
With suitable software (see my page about I2C) you could configure for interrupts and read any of those 64 inputs when they change.