It is not terribly uncommon to be asked about salary history as they are trying to gauge expectations. I think it is a completely immature, B.S., not-well-thought-out approach, but I get the sense that it had been so common for a while that people do it because they don't know any better and haven't thought too much about it. Or perhaps they read a blog that said all the cool kids are asking about salary history and that's good enough for them. However, I don't think I have ever heard of someone requesting a salary sheet. My experience has been that it was simply a blank to fill out in the job history section of the application.
As has been mentioned in at least one other answer, you probably should not have falsified information in the first place. But, that doesn't mean you need to cancel the process at this point. This is an opportunity to have a good discussion with the head of engineering to either improve the situation or to at least figure out that this isn't the right place for you.
I would certainly refuse to provide them any salary sheet or pay stub or any documentation as "proof". The fact is, they have work that needs to be done and it is worth a certain amount of money to the company to get that work done (within a small range, of course). Your ability to uphold your end of the agreement (i.e. I provide labor for some amount of compensation) is not dependent on how much money you made in the past. Either you can do the job or not.
So, you need to have a discussion with the head of engineering (not email; it needs to be real-time discussion, preferably in person, or at least over the phone) about this request. You need to explain that you are not going to provide the salary sheet because they should not have requested it in the first place **. You should ask him how that information is relevant to this process. And, if this person keeps pushing for it, then if you can do so in a non-combative way, ask them how, if the salary they are offering can change based on a factor that is not relevant to the job itself, then could the salary amount being offered also change based on your gender, age, race, etc? Those are also factors that are irrelevant to your ability to perform this job, and if they are going to be subjective on one level, can you trust that they aren't being subjective on those other levels? Skill and experience do affect how productive you might be, and so it makes sense to pay more for a more skilled and/or experienced candidate, but salary history does not directly correlate to either skill or experience, and so it should not be used to gauge such things.
So again, have a conversation to explain that you won't be providing it because you should be compensated for what you are going to do for them, not for what you did for previous employers. And if this head of engineering says that it is a hard requirement that you provide this proof, then you can politely cancel the interview process, explaining that such a requirement indicates to you that this is not a company that strives to treat its employees fairly, and that if this is how the interview process works, then you aren't convinced that, when it comes time for your annual review, that you will be evaluated based on what you actually did rather than some other arbitrary factor(s).
** Since you have already answered their question about prior salary, you might need to fess up about providing "inaccurate" information due to knowing how it would be used and not wanting being underpaid previously to cause you to be underpaid again. You can explain that part of why you are seeking a new position is due to being underpaid, and so you provided them with the amount that you should have been paid. And, if they are willing to pay X if you can prove that you are making Y, then they should be willing to pay X period, End.Of.Discussion.! Sure, you might be dealing with folks who have a narrow/immature world view who might themselves feel "cheated" to give someone a huge pay raise (in which case, do you really want to work for these people?). Or, conversely, you could be dealing with folks who have good heads on their shoulders and realize that paying people what they are worth helps when it comes to employee retention. Not to mention that in cases where paying someone what the job is worth results in a substantial raise due to the person being previously underpaid, that the person is highly likely to come in with a very positive attitude, get lots of work done, and appreciate the company enough to stay for a while. However, given that they are asking for a salary sheet, it is more likely the former. But hey, no harm in having that discussion ;-).
I have been in this situation myself. I had spent 7 or 8 years working at start-ups, each of which I was a co-founder of, hence I got paid the least as the employees all had to be offered market wages. Filling out a salary history would (quite unfairly) put me at a huge disadvantage. So, I just left those boxes on the application empty, and if the company felt strongly about it they could ask, else they could ignore it. One time I interviewed at a company where the HR staff was out of town due to a recent acquisition and so a VP of Engineering took on that part of the interview process. This person asked for my prior salary. I asked, "How is that relevant? Shouldn't you pay me what the job is worth?" To which this person replied, "It's relevant because if you made much more than the range for this position, then you wouldn't accept the pay cut. And if you made far less than the range of this position then { something_stupid_that_I_cannot_remember }." Their reasoning was highly flawed on both points. People often take salary reductions for various reasons, and it is up to the candidate, not the potential employer, to decide if a pay cut is acceptable or not.