MiR,
The .flash file should be a standard .SREC file, and looks like one to me. See the boot-loader sources in components/altera_nios2/sdk/src/boot_loader_sources, particularly the comments in the .S file.
When I build a flash for use with a parallel (CFI) flash chip then my .flash file contains a bootloader followed by the data blocks for the bootloader to write into memory. Each of these consists of length, address, data as you suggest.
For EPCS the bootloader is stored in an on-chip ROM so the .flash file here should contain a set of data blocks, each containing length, address, data. This sounds like what you've got. This data stream needs to be added on to the end of the data stream for the .sof file, becaue the bootloader (within the .S file) starts reading the data blocks from here. It sounds as though elf2flash is starting from offset 0 because it doesn't know the real start address where the data blocks should be stored.
If you can work out how big the device configuration data is then you should be able to add the offset manually and merge the files using objcopy. I know this isn't ideal but it may be easier than writing your own boot loader.