> In those cases, all the "dirty" labor is done by legal/illegal immigrants that are not eligible for said basic income and thus willing to work for much less.

So the introduction of a basic income would make demand for illegal immigrant labor increase. By standard economics, this means that the price of illegal immigrant labor would increase, so even the illegal immigrants would benefit. Sounds like a win/win to me.