I started designing this, designed one using transistors instead, and built half of that.
But I think you can built an 8-bit relay version of my 16-bit transistor CPU core with on the order of 400 DPDT relays, which is on the order of $1000, plus a comparably big bag of diodes, which is much less than $1000. This includes registers (10 of them), control and sequencing logic (including a diode microcode matrix), but not RAM, which you wouldn't want to make from relays. (To make an 8-bit version you'd probably have to add another 3 upper address registers, to still have 16-bit addresses.)
But I think you can built an 8-bit relay version of my 16-bit transistor CPU core with on the order of 400 DPDT relays, which is on the order of $1000, plus a comparably big bag of diodes, which is much less than $1000. This includes registers (10 of them), control and sequencing logic (including a diode microcode matrix), but not RAM, which you wouldn't want to make from relays. (To make an 8-bit version you'd probably have to add another 3 upper address registers, to still have 16-bit addresses.)