I have posted this question, so that I can put the answer up, as I have in fact found the solution to my own issue.
The potential RDC issue caused by booting the M4 then booting Linux seems to be resolved by putting PCIe into uBoot.
We had not put PCIe into our uboot, as our uboot does not need to do anything with out PCIe device and does not have drivers for it anyway. Therefore in out uboot build config we had not set:
CONFIG_PCI
CONFIG_CMD_PCI
CONFIG_PCIE_IMX
With Linux on its own, this does not cause an issue. However, as soon as you boot the M4, there is something happening with the RDC that means that it blocks access to the PCIe for the A9 Linux.
The solution is to ensure you have PCIe built into your uboot image (with the 3 above config options).
Now when you boot the M4 from uboot, the PCIe is not blocked, so it means that Linux boots successfully, and configures the PCIe correctly.