If you don't have all of your paystubs, that's usually not critical if your payroll is handled by a reasonably competent system - there should be a yearly aggregate that can display totals to date.
If you don't have paystubs, your other option is to ask IRS for copies of four 1040 and W-2 summaries for a given year. It may not be what USCIS asked for, but it should provide evidence that you were getting paid.