Родился 2 февраля 1913 года в селе Решеты ныне Кочковского района Новосибирской области в бедной крестьянской семье. Украинец.
В 1931 году приехал в Москву и работал электросварщиком на одном из предприятий города, одновременно учился на рабфаке художников.
В 1940 году окончил Московский архитектурный институт. Работал архитектором на Московской сельскохозяйственной выставке.
В Красную Армию призван в январе 1941 года. Участник Великой Отечественной войны с июня 1941 года, принимал участие в боях под Смоленском.
Под натиском гитлеровских полчищ вместе с воинской частью отступал на юго-восток.
В сентябре 1941 года близ села Воздвиженское на Сумщине был тяжело ранен. Местные колхозники скрывали его в селе и лечили. Когда в начале 1942 года на хуторе Говорунов появились партизаны-ковпаковцы, С.П. Тутученко и его товарищи сразу же влились в их отряд. В одном из боев под Путивлем захватил у гитлеровцев ротный миномет и беспощадно уничтожал врага этим грозным оружием. Некоторое время был в комендантском взводе.
Затем он стал начальником штаба отдельного кавалерийского эскадрона Сумского партизанского соединения. Участвовал в рейде ковпаковцев в Карпаты. Эскадрон под его командованием захватил 500-метровый мост через реку Буг, чем содействовал успешной переправе соединения через реку.
Указом Президиума Верховного Совета СССР от 7 августа 1944 года за проявленные доблесть и героизм в боях с немецко-фашистскими захватчиками Семену Павловичу Тутученко присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда».
С 1944 года капитан Тутученко – в запасе. После Великой Отечественной войны С.П. Тутученко работал архитектором. Был секретарем Союза архитекторов СССР, руководителем сектора теории архитектуры Киевского научно-исследовательского института теории, истории и перспективных проблем архитектуры. Член ВКП(б)/КПСС с 1949 года.
Кандидат наук, заслуженный архитектор УССР, автор более 80 научных работ. По его проектам построено более 100 сооружений, 17 монументов партизанской славы. В их числе – дом правительства в городе Кишиневе, памятник «Героям Сумщины» в областном центре Украины городе Сумы, памятник «Партизанам-ковпаковцам» в городе Яремче, памятник С.А. Ковпаку в городе Путивле, жилые дома в городах-героях Киеве, Севастополе и других. Жил в городе-герое Киеве. Награжден орденами Ленина, Красной Звезды, Отечественной войны 1-й степени, медалями, а также польским орденом Золотой Крест «Виртуги милитари».
Скончался Семен Павлович 4 января 1994 года. Похоронен в Киеве на Байковом кладбище.
В Новосибирске имя Героя Советского Союза Семена Павловича Тутученко увековечено на Аллее Героев у Монумента Славы [179, 240, 304, 426, 787, 943, 1240].