I can tell you that I've successfully used the ENC28J60 with Arduino Mega and the UIPEthernet library but it's been a long time since I messed with that chip (I've been using W5100 and W5200 instead) so I can't remember the exact details.
Just for a lark, try wiring the ENC28J60 CS pin to pin 10 on your Mega to see if it might be hardcoded to that pin, as is the Arduino Ethernet library. That would make some sense as UIPEthernet is meant to be a drop in replacement for the Ethernet library.