Initially I tried to get FatFs running with 1Mbit worth of NOR Flash, which would have provided enough storage for the small amount of data. Just not for the file system itself... Seems like the smallest size for any FAT volume with 4096 bytes sector size is 528 kilobytes or just over 4Mbit.
So I ditched that and went for a 16Mbit SST25VF016B instead. A fair amount of debugging later, and whaddaya know?