Using large parts of a research paper I am writing a (maths) paper that generalises an earlier work, and aplies it to something slightly different.

The problem is, I am literally having to step through the previous paper, and point out how the more general case would differ. My paper is therefore essentially entirely based on this work (though there are substantial chunks here and there whcih are original). I am not entirely sure how to approach this case. On other SE posts, it suggests to paraphrase. That is clearly not suitable in this case.
You should note that you can use all of the ideas of the other paper, so long as you give proper attribution and citation so that you don't claim the original as your own. You can't, however, use "too many" of their actual words and must quote and cite the ones you do. The first issue is plagiarism and the second is copyright. Be sure to avoid both. 

But if you write a proof that has the same structure as the other, using the same lemmas and referencing the same earlier work, it shouldn't be a problem, especially as you say you will explicitly state that the overall structure is the same. 

You don't need to work to make it seem different where it isn't. For some sorts of things, especially in math, there may be, in essence, only one way to properly state something. This is recognized both in law and in practice. 

However, it is possible that reviewers will suggest to you that your work isn't especially novel and may want to reject it on that basis. But if your conclusion is sufficiently interesting, and you support that idea by making it explicit, you may avoid that pitfall also.