Ersten Kunstunterricht erhielt Paul Meyerheim durch seinen Vater, Eduard Meyerheim (1808-1879) - bekannt als Maler von minutiösen Biedermeier-Genrebildern aus dem Leben der Kleinbürger und Bauern -, seine weitere Ausbildung erfolgte 1857-60 an der Berliner Akademie der Künste. Anfangs vom Stil seines Vaters beeinflusst, wandte sich Paul Meyerheim später Adolph v. Menzel (1815-1905) und der Schule von Barbizon zu (die Künstlerkolonie, benannt nach einem Dorf am Rande des Waldes von Fontainebleau, beeinflusste maßgeblich die Landschaftsmalerei in ganz Europa), die er 1865-66 in Paris kennen gelernt hatte.
An der Berliner Hochschule für Bildende Künste leitete Paul Meyerheim seit 1883 die Tiermalklasse und an der Berliner Akademie der Künste hatte er seit 1887 einen Lehrstuhl inne.
Neben Landschaften schuf Paul Meyerheim Porträts, Genre- und Tierbilder. Für die Tierbilder fand er seine Motive im Berliner Zoologischen Garten; besonders gern stellte er Affen, denen er häufig menschlich-parodistische Züge verlieh, und majestätische Löwen dar, was ihm den Beinamen „Löwen-Meyer“ eintrug. Außerdem war Paul Meyerheim als Holzschneider und Lithograph tätig.
Zu Paul Meyerheims bekanntesten Arbeiten gehört der Bilderzyklus, den er 1872-75 für die Gartenloggia der Villa Borsig in Berlin-Moabit schuf. Der Entwurf für die Loggia stammte von dem königlichen Hofbaurat Johann Heinrich Strack (1805-1880). Sechs der auf Kupfertafeln gemalten Bilder thematisierten Szenen aus der Lokomotivproduktion, das siebente zeigte die Familie Borsig beim Erntefest. Als ab 1896 das Unternehmen Borsig den Industriestandort in Moabit aufgab, mussten 1911 auch der Park mit Villa und Gewächshäusern der Neubebauung mit Wohnhäusern weichen. Einige der Kupfertafeln aus dem Bilderzyklus haben die Umsetzung der Loggia von Moabit in den Tiergarten und den dortigen Abriss 1954 überstanden und befinden sich heute im Besitz des Märkischen Museums und des Deutschen Technikmuseums Berlin.