Those CPUs should be more than enough for a Voodoo2 SLI setup. The Voodoo2 SLI setup performs slightly worse than a V3 setup...perhaps about the same as a V3 2000 16MB, but with more memory.
Personally I'm runing a Celeron 566@850 with a 175MHz Voodoo3 3000 AGP card, and on Q3A 1.31 running at 800x600 with custom graphical settings, I'm getting around 70-80FPS on demo FOUR, so you should be expecting maybe around 50-60FPS on a V2 setup on the same settings.