I proved two lemmas that I need both in two different papers. The two papers will be submitted in the same period. Is it justifiable to include the SAME proofs of the two lemmas in the two different papers, instead of including the proofs in one and then referencing to the other
This would depend on the length and complexity of the proofs. You would have to cross-reference the lemmata whether you include the proofs or not. Since Math editors are experienced people, they will understand your problem.
The argument against including proofs in both papers is redundancy. The argument for including proofs in both papers is self-containment.
Sometimes, you can compromise and give the proof-idea in one paper and a full proof in the other.
Your situation is complicated because there is no guarantee that both papers will be accepted. In Computer Science, we could solve this with a tech report. These days, arxiv will serve you well. Thus, you would publish a preview of both papers that you then can withdraw once your papers have been accepted.
In addition to the issue of self plagiarism, which is solved via citation, there is the possibility of copyright issues. Normally when a paper is published the publisher takes over the copyright, yielding a license for some things back to the author(s).
So, when the first paper is published, containing the proof of the lemma(s), the copyright is now held by that publisher and even the author needs to respect that, limiting how much can be copied from the first paper into the second, even with citation.
The issues are less if the same publisher publishes both papers, but even then some permission is probably required.
If both papers are to be submitted simultaneously (or nearly so), you may need to finesse this a bit. For first submissions, include everything in both papers, but give notice to the editor that changes will need to be made if the other paper is published first. Once the first paper is published (unlikely that such would be simultaneous given how publishers work) provide an updated version to the second paper with the proof removed and the reader referred to the first paper for details.
This would give the reviewers complete information on which to base the review and not result in either self plagiarism or copyright issues.
Short version: Use the time to publication to your advantage to make both papers consistent with all applicable rules.
It might be useful in some ways to delay submission of one of the papers until you get some indication from the publisher on the likelihood of publishing the other. You then have more information on which to proceed.