Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong. 

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.