Airline-specific upgrade requirements vary, usually around 2500 total time with some turbine time, but you don't have to get that time at the airline in question...it can come from another 121, 135 op, military, or even 91, as long as you have it. So mesa street captains are not CFI's, they have time from somewhere else.

Also the airline requirements are just that...airline requirements, not FAA requirements. As long as you meet ATP mins (1500 total time and other stuff), the airline can upgrade you.

Foreign operations (excluding Canada) require a couple extra things...
1) SIC type rating for the FO
2) The CA must meet ICAO ATP requirements, which include 1200 hours PIC...this has kept a lot of low time FO's from upgrading at some airlines. Some of them have to go rent cessnas on their days off to get their time up