A P ℓ -decomposition of a graph G is a set of pairwise edge-disjoint paths with ℓ edges that cover the edge set of G . In 1957, Kotzig proved that a 3 -regular graph admits a P 3 -decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an ℓ -regular graph to admit a P ℓ -decomposition, for odd ℓ . Let g , ℓ and m be positive integers with g ≥ 3 . We prove that, (i) if ℓ is odd and m > 2 ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every m ℓ -regular graph with girth at least g that contains an m -factor admits a P ℓ -decomposition; (ii) if m > ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every 2 m ℓ -regular graph with girth at least g admits a P ℓ -decomposition. Furthermore, we prove that, for graphs with girth at least ℓ − 1 , statement (i) holds for every m ≥ 1 ; and observe that, statement (ii) also holds for every m ≥ 1 .