Фамилия Лелёхина — женская форма фамилии Лелёхин, а та, в свою очередь, образована через суффикс -ин от прозвища или нецерковного имени Лелёха. В русской ономастике суффикс -ин традиционно присоединялся к основам на -а, -я и указывал на принадлежность: Лелёхин буквально значил «сын Лелёхи» или «человек из рода Лелёхи». Модель типична для северных и центральных регионов России, где притяжательные фамилии на -ин встречаются чаще, чем на -ов.

Корень здесь — «лел-». Самая прямая версия связывает прозвище Лелёха с диалектным глаголом «леле́кать» — ласкать, нежить, заботливо ухаживать. В говорах Вологодчины и Архангельской области «лелёха» — это ласковый, изнеженный человек, иногда — любимчик, баловень. Так могли прозвать младшего ребёнка в семье или того, кого особенно баловали. В этом случае фамилия несёт отчётливо ласкательный оттенок, что для русских прозвищ редкость: чаще они бывают ироничными или нейтральными.

Менее вероятная, но допустимая версия — связь с глаголом «леле́ять» в значении «качать, убаюкивать». Тогда Лелёха — это дитя, которого укачивают, или сама нянька, но для женского прозвища форма на -а в мужском роде нехарактерна. Есть и гипотеза о происхождении от дохристианского имени Лель (славянское божество любви и брака), но она слабая: имя Лель фиксируется в источниках крайне редко, а форма Лелёха из него не выводится без натяжек.

Фамилия Лелёхин и её женский вариант Лелёхина — довольно редкие. Они встречаются в основном на Русском Севере и в Поволжье, что подтверждает диалектную природу основы. В списках жителей Вологодской и Костромской губерний XIX века такие фамилии единичны. Сословной принадлежности у фамилии нет: Лелёхиными могли быть и крестьяне, и мещане, и священники — суффикс -ин не даёт подсказки о социальном статусе, в отличие от -ский.

По написанию фамилия устойчива: ударение падает на второй слог — Лелёхина. Вариант с буквой «ё» обязателен, иначе теряется смысл: «Лелехина» без точек над «е» читалась бы с ударением на первый слог и отсылала бы к совсем другой основе (например, к имени Лель или к слову «лелеять» в ином значении).