Quebec,
I searched the Ancestry on-line Irish RC baptism records for Sarah McELvar (and variants) born c 1838 but did not find a match. Not every parish in Co Derry has records for the 1830s and so the conclusion is that she may have been born in one where there are no records. No easy way around that.
Knowing that the family was RC, I have given you details of the parishes where there were McElvars/MCilvars of that denomination in 1831. You might want to focus your research on them.
You mentioned that Sarah’s mother was possibly named Mary McLemme or McKenna. The name McLemme is unknown in Ireland (to me anyway) and so I feel it’s likely there has been a misinterpretation somewhere. McKenna is quite common and is a more likely possibility.
I did find this death but have no idea whether it’s your family.
https://civilrecords.irishgenealogy.ie/churchrecords/images/deaths_returns/deaths_1879/06532/4882421.pdf
Possibly DNA testing may be a way of matching with others who have additional information about where the family originate. Family Tree DNA reportedly has more people with Ulster roots than any other company. That obviously increases the chances of finding a match. You might want to try them or, if you have already tested, you can transfer your results to them for no fee.
The North of Ireland Family History Society is running an Ulster DNA project in conjunction with FTDNA and can offer testing kits at a reduced price. http://www.nifhs.org (Go to DNA project on the website).