A negative result for that function is indeed possible. It indicates that you are trying to use more memory than you have.
The value returned is the difference between the start of the heap and the location of the stack.
If you allocate too many global or static variables then it is possible for the heap start to be very close to where the top of the stack is, and as your program runs and local variables are allocated and the stack used by function calls, the stack pointer can end up lower in memory than the start of the heap.
So you end up with a negative value.
Further to that, the stack smashing into the heap like that causes memory corruption and strange things happen to your sketch.
Assuming you got the 5 volt version, hook up should be straight forward, although a bit cumbersome and it will likely require you to write some code.
Connect the address, data, and enable pins from the flash to digital IO pins on the Arduino. Also connect the chip's Vdd to the Arduino +5VDC pin and the chip's Vss to an Arduino ground pin.
Configure all the pins connected to chip's address lines and enable lines to be digital out.
To read a byte from the memory:
1) Configure the pins connected to the chip's data lines as digital input.
2) Set the pins connected to the address lines to the address you want to read.
3) Set the enable lines to CE=0, OE=0.
4) Read the data byte from selected address from the pins connected to the data lines.
To write to the memory is similar but more complicated because flash requires you to erase a whole sector before you can start writing bytes inside that bank. You also need to wait for the write operation to complete, which typically takes ~20us for this chip.
All the reading and writing sequences are well documented in the data sheet here...
http://ww1.microchip.com/downloads/en/DeviceDoc/25022A.pdf
Be sure to publish your code so others in the same situation will not have to start from scratch!
Best Answer
The only thing that you have to do is perform logic level shifting. This is because the MR2A16A is a 3.3V powered device and looking at page 7 of the datasheet it shows the max input high voltage i.e. VIH. This is less than the max output voltage of the arduino (~5v) so you will risk damaging the MRAM if you don't level shift. As for the data pins since you have to read and write from them you would need bi-directional level shifting.For the address lines a simple unidirectional shifter would work. But with this many lines to apply level shifting on, it may be cumbersome.
The method of level shifting depends on the speed of your intended communications. Simple voltage dividers can work for slow signals but will not work for fast changing signals. There are ICs for this but it's entirely up o you if you get those or go DIY.