The format of the data on the flash depends on what the boootloader code expects.
Since you don't want it to be anywhere near the size of an S record file (which is probably 3 characters/bytes for each data byte).
I suspect the bootloaded needs address:length:data triplets - all as binary data with some defined endianness (etc).
Personally I'd either write a bootloader that can directly process the ELF image (having stripped out all the unnecessary sections), or write a program to extract the loadable program segments together with their offsets and sizes to make a smaller file.
I wouldn't go via S record format at all!
I actually suspect that the Altera boot code can only load to one contiguous block of memory.
This is rather sub-optimal in the extreme if you are trying to load code into tightly coupled instruction memory and also initialise multiple separate data areas.