Сочетание не спеша представляет собой пограничное явление. По форме это деепричастие, по функции — наречие. Как наречие не спеша охарактеризовано в «Русской грамматике» 1980 г. В правилах орфографии оно часто включается в перечень деепричастий (как форма глагола):
Отрицание не пишется раздельно в следующих случаях.
1. Со всеми формами глаголов (кроме полных причастий; о них см. § 150):
а) с инфинитивом и спрягаемыми формами, напр.: не знать, не знаю, не знаете, не знал, не знали, не торопишься, не торопимся, не торопись, не нравится, не повезло;
б) с краткими формами причастий, напр.: не использован, не накрахмалено, не откупорена, не разработаны, не закрыто, не занят, не выпито;
в) с деепричастиями, напр.: не желая, не отвлекаясь, не спеша, не шутя, не успев, не встретившись.
(Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М. Любое издание)