Why is that in the constitution?
As it turns out, it isn't. The constitution is silent on the treatment of tied votes for local elections, which may account for the mechanism used to resolve the 1988 mayoral race in Estancia, but it is explicit about statewide offices. Article V, Section 2:
The returns of every election for state officers shall be sealed up and transmitted to
the secretary of state, who, with the governor and chief justice, shall constitute the
state canvassing board which shall canvass
and declare the result of the election. The
joint candidates having the highest number
of votes cast for governor and lieutenant
governor and the person having the highest number of votes for any other office,
as shown by said returns, shall be declared
duly elected. If two or more have an equal,
and the highest, number of votes for the
same office or offices, one of them, or any
two for whom joint votes were cast for governor and lieutenant governor respectively,
shall be chosen therefor by the legislature
on joint ballot. (As amended November 6,
1962.)
Because of the 1962 amendment, I sought out an earlier version; here's the version as of 1912:
The returns of every election for state officers shall be sealed up and transmitted to the secretary of state who with the governor and chief justice shall constitute the state canvassing board which shall canvass and declare the result of the election The person having the highest number of votes for any office as shown by said returns shall be declared duly elected If two or more have an equal and the highest number of votes for the same office one of them shall be chosen therefor by the legislature on joint ballot
In a comment, divibisan points to NM Stat § 1-13-11, which does call for deciding ties by lot. However, since it mentions "county canvassing board," singular, it reinforces the suspicion that it does not purport to supersede the mechanism specified in the constitution for statewide offices:
In the event of a tie vote between any candidates in the election for the same office, the determination as to which of the candidates shall be declared to have been nominated or elected shall be decided by lot. The method of determining by lot shall be agreed upon by a majority of a committee consisting of the tied candidates, the county chairmen of the political parties that participated in the election and the district judge. The county canvassing board shall issue the certificate of nomination or election to the candidate chosen by lot.
This perception is also reinforced by the fact that it is situated among several sections that concern "county canvass," with "state canvass" appearing only a few sections later.