Родился 9 января 1930 года последним, восьмым, ребёнком в семье. Детство прошло в посёлке под Ярославлем. Был слабым ребёнком, болел рахитом, но благодаря занятиям спортом излечился. Рано пошёл работать — пилил брёвна на дровяном складе, работал на токарном станке.
Закончил Малаховский техникум физической культуры. Выступал за «Динамо» (Москва).
14-кратный чемпион СССР (1956, 1957, 1963 в гонках на 15 и 30 км, 1963 на 70 км, 1953—1955, 1957, 1964 в эстафете 4?10 км).
Серебряный призёр чемпионата мира 1958 года в гонках на 15, 30 км и в эстафете 4?10 км. Бронзовый призёр чемпионата мира 1962 года в эстафете 4?10 км. Победитель Холменколленских игр 1958 года в гонках на 15 и 50 км.
Чемпион Олимпийских игр 1956 в эстафете, показал в ней лучший результат на этапе среди всех спортсменов. Тогда же получил бронзовые награды в гонках на 30 и 15 км. Бронзовый призёр Олимпиады 1964 года в эстафете.
Окончил ГЦОЛИФК (1968). Тренировал лыжную сборную СССР в 1968—1976 годах. Первым начал использовать в подготовке лыжероллеры и тренироваться на опилочной лыжне. Самый известный ученик Павла Константиновича Колчина — «звезда» советских лыжных гонок конца 1960-х — начала 1970-х годов Вячеслав Веденин, ставший под его руководством двукратным чемпионом мира (Высокие Татры—1970) и двукратным олимпийским чемпионом (Саппоро—1972).
С 1954 года женат на олимпийской чемпионке Алевтине Колчиной (род. в 1930 году). Написали вместе с ней книгу «О лыжах и о себе» (1978). В середине 1980-х годов переехали на хутор близ города Отепя в Эстонии, в котором всю жизнь (в детстве с няней) живёт их единственный сын Фёдор (род. в 1957 году) — чемпион СССР по лыжному двоеборью, участник Олимпийских игр 1980 года в Лейк-Плэсиде (15-е место). Участвовали в создании отепского центра подготовки лыжников. В середине 1990-х годов Колчины получили эстонское гражданство за особые заслуги.
Умер 29 декабря 2010 года.