В общем, пока реализовал такой алгоритм: исходный звук нарезается на окна (например по 4096) отсчетов, на окно накладывается оконная функция, можно использовать функции Хамминга, Хеннига, Блекмена. Окна берутся с перекрытием (в случае прикрепленных примеров перекрытие 75 %). Для ускорения часть исходных окон "выкидывается", но компануется все с тем же 75% перекрытием.
Качество для изменения темпа речи выходит сносным. Никакого БПФ. Примеры прикрепляю.
Хотя, хотелось бы надыбать более качественные алгоритмы...