Well, technically, the fossil remains of a stegomastodon. Close enough.
Elephant Butte Reservoir was named after Elephant Butte, a mountaintop that, viewed from a certain angle, and with a lot of imagination, sort of looks like an elephant. Being in the middle of North America, we never dreamed that there might be a real pachyderm lurking in the bushes! (Or the rock formations.)
"like a robust version of the modern elephant. It weighed about 6,000 kilograms (13,000 lb). "
Holy cow.
Elephant Butt Lake! 
They are digging up the skull. Did not say if they found the other end. 
Ah, understand now. I think. Out in the middle of the desert basin called Jornada del Muerte, on the outskirts of Alamogordo, there is or was a dive shop – at least, the building had the red square with the diagonal white stripe painted large on the front. It looked so incongruous. Elephant Butte lake is still nearly two hours from there by road, but at least is makes a whisker of sense. Like the Seattle Coffee shop in T-or-C, New Mexico seems full of incongruities.
We still have not found that left turn in Albuquerque, though.
Elephant Mountain, Barstow, CA.
New Mexico and Arizona are the two driest states in the union, yet have more boats per capita than any other states.
Scuba diving is quite popular. Swimming in the lake, it is an immense green mass, with visibility measured in inches. Divers tell me that, about six feet below the surface, the temperature drops sharply, the algae disappears, and the water is crystal-clear.
An interesting geographical manifestation of Nominative Determinism
Once, I should have taken a left turn in Santa Fe. I was pretty sure I wasn’t on the right road to Alamosa but I didn’t have GPS so I decided to keep driving at least until there was a road sign to let me know what road I was on. Then I drove over a ridge and suddenly saw the canyon of Taos right smack in front of me. I had never been there, but recognized it from pictures so I knew where I was. So I stayed there instead because it had hotels.
I am skeptical that you ever can be on the right road to Alamosa.
Well, if you know any divers and they find a pair of 50 year old kids glasses down there… those are mine. I can vouch for that thermocline. After the glasses fell off of my face I dove in the water and followed them about 15 feet down until I was worried that a giant craw-fish might get me. (hey, I was ten). very cold.
That’s not actually all that impressive - that’s about the average size of an average modern elephant, which generally come in between 7 and 11 feet tall, and somewhere around 3 tonnes.