The e-verify program is one of those subtle Trojan Horses that government is so good at.
It starts with a widely perceived problem that has widespread support: that the country is full of illegal workers.
Whether or not this is actually a problem is a matter that can be debated, but that's not actually the relevant bit. The relevant bit is that it's popularly seen as such in many quarters.
The solution looks simple: create e-verify.
All employers are required to check citizenship/work eligibility when hiring.