Error flashing the QSPI NOR Flash connected to HPS with Command shell

Then you could have the same problem than me. I don't know if quartus_hps has an option to reduce the SPI frequency, but if it does it is not documented so only Intel can answer that question.

My current solution is to upload the preloader and our flashing software (based on Redboot) through JTAG first and then use our software to write to the flash.

You could also try a Cypress/Spansion chip but it's not that easy to change a BGA chip on a PCB without specialized equipment.