You are right that we know nothing about the application in question - details here would make it much easier to give recommendations.
I mentioned 4MB flash as it is the HW spec. This 4MB gets filled over a period of time.
Details of application - I have data packets each 32 bytes in size and we have accommodate 2000 of these (predefined). This I plan to put in a part of the 4MB Flash. Rest of the memory will be used for storing records comprising of these data packets with data and time etc. The records will be deleted from time to time but the data packets will remain. It is possible to use a long int as an address pointer from the start of the available memory (after the data packets)
and store records. I still curious to know how one can create a section larger than 64K.