ok, so i am in a slightly different situation than the guys above and from my understanding so far i will explain my issue and potential solution that i have seen online. I am from Pakistan, but i believe this should work for other nationalities as well.
So I am in Canada for a Phd, my wife had a change in her surname after she got married. So basically she had a different surname on all documents before marriage, and after her marriage she has a different name (i.e. different name for last 5 year period). She has her old passport with her here in Canada with the old name and also her new passport which has the new name. We also have our marriage certificate that has her old name.
So we intend to submit her old passport and new passport, old drivers license and new drivers license, and explain in the LOE that the change happened after marriage (will also submit the marriage certificate which has her old name).
Now this takes care of the LOE part. They ask if we have a document for name change. There is no official document for that with us at least. So I searched around and it turns out that you can write a letter stating that you are the same person who has had different names at different points in time. Explain that your name before marriage was XXX, now it is XYZ. Then you sign that document in the presence of a notary official who wil put their stamp and sign on it, which implies that you made this solemn declaration that you are the same person who has used different names and admitted this in front of this notary official. This is getting your document notarized. You can check redseal notary in canada, especially if you are around in the GTA area in canada.
So basically this notarized document is an admission from you (along with the LOE) that you are telling the truth and furnishing the best proof possible.
I believe this is the way to go. Somebody please correct me if I am wrong, but i am going to be doing this soon for my wife here and submit my documents.