@filmore, you might try the New Mexico State Land Office map (NMSLO) https://mapservice.nmstatelands.org/OilGasMinerals/
or the NM State Land Office Lease Search NMLeaseSearch
Also, WellDatabase has a lease search feature.
If you would like to post one of the actual lease numbers someone may have the resources to give a few more clues.