Ok. Turns out it’s standard flash performance issues when storage fills up
I did a benchmark, then free’d up 4GB of space on internal storage and benchmarked again - time for random writes dropped by almost half. Going from 88 IOPS to 144 IOPS.
I put the device on Airplane mode and closed other apps to try to keep performance relatively constant.