Low power memory?

What you shall do - calculate needed power to fill selected (SPI flash? SD card?) memory with 6-8MB of data at full speed in one pass. Then you have starting info to think about. I guess that 110mAh could be enough to do what you need using some kind of buffering and periodically writing whole buffer of let's say, 256 bytes data.

Surya Prakash Sharma said:

most of the memory I've been able to find needs a good 20mA or more for programming

Taking 20mA, 16 hrs would mean 320mAh if you were writing 100% of the time. But how much of the 16hrs are you actually writing to the memory, especially if you collect data for a whole chunk? I bet only a small fraction of the time.
8MB means 0.5MB per hour. That means one 512 block every 3.6s. Writing will perhaps take 36ms, so you only need the 20mA for 1/100 of the time, or 3,6mAh in 16 hrs. Does this sound better?

To ensure that that the high peak current won't pull the battery voltage down, you should put a resistor between battery and memory chip and attacha larger capacitor. So the capacitor can charge over time and this then drained by the write without applying a high load to the batery.

Surya Prakash Sharma said:

logging 6 sensors at 1Byte each, 15Hz

6*15 = 90 bytes/second = 512 bytes every 5.7 seconds. So the duty cycle is in your favor even more than Jens -Michael suggested.

You want to look at what is the standby current of the external memory and the dynamic current during programming. Those plus the duty cycle will give you your average current.