Родился 13 ноября 1830 года в Лейпциге, где его отец, обер-камергер, член Государственного совета, граф Андрей Петрович Шувалов (1802—1873) и мать Фёкла (Текла) Игнатьевна Валентинович (1801—1873), в первом браке за П.А.Зубовым, находились в отпуске. Братья и сёстры: Пётр (1827—1889, член Государственного совета), Софья (1829—1912, замужем за членом Государственного совета А. А. Бобринским), Ольга (1833—1859).
19 ноября 1841 года Павел Шувалов был зачислен в пажи, 25 июня 1848 года произведён в камер-пажи и 4 сентября того же года был зачислен в Пажеский корпус. По окончании курса наук в Пажеском корпусе 26 мая 1849 г. был произведён в корнеты и зачислен в лейб-гвардии Конный полк. В кампании того же года против венгров участвовал в походе гвардии к западным границам, однако в военных действиях против повстанцев участия не принимал.
11 июля 1854 года был назначен адъютантом при великом князе Николае Николаевиче и участвовал в Крымской кампании. В сентябре и октябре 1854 года состоял при главной квартире главнокомандующего Южной армией князе М. Д. Горчакове, а с октября 1854 по февраль 1855 года находился в осаждённом Севастополе и за отличие в сражении с англо-французами при Инкермане был награждён 24 октября 1854 года орденом св. Анны 3-й степени с мечами. Кроме того, за оборону г.Севастополя был произведён 6 декабря 1855 года в штабс-ротмистры и 26 августа 1856 года получил орден св. Станислава 2-й степени.
12 апреля 1859 года Шувалов был произведён в ротмистры и через несколько дней получил назначение состоять по Военному министерству и военным агентом во Франции с переименованием в подполковники; находился при Наполеоне III во время Итальянской войны. 8 сентября того же года пожалован званием флигель-адъютанта. За отлиное выполнение дипломатических поручений при французском дворе Шувалов был 17 апреля 1860 года произведён в полковники.
15 июля 1861 года был назначен исполняющим дела директора Департамента общих дел Министерства внутренних дел и принимал активное участие в работах по освобождению крестьян от крепостной зависимости, 30 августа того же года был удостоен ордена св. Владимира 4-й степени. 25 мая 1863 года назначен командиром лейб-гвардии Стрелкового Его величества батальона, во главе которого принял участие в подавление польского восстания.
30 августа 1864 года Шувалов был произведён в генерал-майоры с зачислением в Свиту его величества; 24 ноября 1864 года назначен командиром лейб-гвардии Семёновского полка. 30 августа 1866 года получил орден св. Владимира 3-й степени.
9 сентября 1867 года назначен начальником штаба войск гвардии и Петербургского военного округа; кроме этого Шувалов, оставаясь в занимаемой должности, был членом Комиссий для рассмотрения вопроса о перевооружении армии, Главного военно-тюремного комитета, Комиссии для составления проекта положения об управлении хозяйственной частью в войсках и, наконец, помощником председателя Главного комитета по устройству и образованию войск; 13 мая 1873 года произведён в генерал-лейтенанты. Находясь на посту начальника гвардейского штаба Шувалов получил ордена св. Станислава 1-й степени (30 августа 1868 года), св. Анны 1-й степени с мечами (30 августа 1870 года), св. Владимира 2-й степени (30 августа 1872 года) и Белого Орла (30 августа 1875 года).
9 августа 1877 года Шувалов был назначен командующим 2-й гвардейской пехотной дивизией. Принимал участие в русско-турецкой войне 1877—1878 гг. и находился в сражениях при Горном Дубняке и на Правецкой позиции; 12 октября 1877 года он был награждён орденом св. Георгия 4-й степени
Шувалов был дважды женат. Первая жена (с 25 июля 1855 г.) — Ольга Эсперовна урождённая княжна Белосельская-Белозерская (1838—1869), её отец был флигель-адъютантом и генерал-майором;
Вторая жена (с 1877 г.) — Мария Александровна урождённая Комарова, фрейлина великой княжны Екатерины Михайловны и гофмейстерина двора великой княжны Марии Павловны, кавалер ордена св. Екатерины 2-й степени, её отец был профессором Института Корпуса инженеров путей сообщения.
Дети П. А. Шувалова от 1-го брака: Андрей (умер в младенчестве), Елена (1857—1943, фрейлина, замужем за генералом от инфантерии Ф. Е. Мейендорфом), Павел (1859—1905, генерал-майор, градоначальник Одессы и Москвы), Пётр (умер в младенчестве), Фёкла (1863—1939, замужем за генерал-лейтенантом Г. Э. Штакельбергом), Мария (1865—1951, фрейлина, замужем за бароном К. К. Кноррингом).
Дети от 2-го брака: Софья (1877—1917, замужем за князем Г. П. Волконским), Александр (1881—1935, титулярный советник), Ольга (1882—1939, фрейлина, замужем за Кутаисским вице-губернатором графом В. А. Ольсуфьевым).