Фамилия Шихалаев — редкий случай, когда географическое происхождение почти наверняка перевешивает все прочие версии. Её основа — имя или прозвище Шихалай. Скорее всего, это кумыкская или тюркская форма, где «Ших» восходит к арабскому «шейх» (старейшина, духовный наставник), а «алай» — тюркский суффикс или часть имени, указывающая на принадлежность («из рода шейхов» или «подобный шейху»). Фамилия образована по русской модели с суффиксом -ев, который в этом случае прикрепили к тюркской основе, что типично для народов Дагестана, где фамилии на -ов(-ев) массово появились в XIX — начале XX века.

Самый вероятный ареал фамилии — Дагестан, особенно Кумыкская плоскость или южные районы, где сильно влияние арабской и тюркской ономастики. Встречаемость Шихалаевых за пределами Кавказа, как правило, результат миграций XX века. Внутри Дагестана фамилия может иметь и лакские корни: у лакцев имя Шихан (от того же «шейх») — не редкость, а форма Шихалай могла быть его диалектным вариантом.

Суффикс -алай в основе — нестандартный для славянских фамилий, но частотный в кумыкских антропонимах. Сравните с фамилиями Шихалеев, Шиханов — все они растут из одного корня. Однако Шихалаев отличается именно формантом: он не просто указывает на «сына Шихалая», а, возможно, фиксирует прозвище человека, которого так звали в быту — с уменьшительным или фамильярным оттенком. В русских документах конца XIX века такие фамилии нередко записывали на слух, поэтому возможны варианты написания: Шихалиев, Шихалаев, Шихаляев. Последний, скорее всего, ошибочный, от диалектного произношения «а» как «я».

Сословная принадлежность носителей фамилии почти наверняка недворянская. Шихалаевы — потомки узденей (свободных крестьян) или духовных лиц, так как корень «ших» часто указывает на родство с мусульманскими священнослужителями. Однако прямых доказательств принадлежности к высшему сословию нет — это фамилия сельской знати или зажиточных общинников, а не титулованных родов.