OK, here is an argument for $p$ odd (I have been [wrongly] assuming $p$ was a prime this whole time).

First, note that the abelianization is $\mathbb{Z}$; this shows is that if $K=[G,G]$, then your group is the semidirect product $K\rtimes \mathbb{Z}$. The first half of the Reidemeister-Schreier theorem shows that $K$ is generated by $b_{i,n}$, where $b_{i,n}=y_0^ny_iy_0^{-n-1}$. The relations are all of the form $y_0^ny_iy_jy_{j+k}^{-1}y_{i+k}^{-1}y_0^{-n}$, where all the first indices are interpreted modulo $p$. If we allow $b_{0,n}=1$ for all $n$, then these relations are all rewritten as $b_{i,n}b_{j,n+1}b_{j+k,n+1}^{-1}b_{i+k,n}^{-1}$. If we think of all the generators in an array, where the columns are indexed by $i$ mod $p$, and the rows indexed by $n\in\mathbb{Z}$, then these relations allow us to "cancel" most of the generators, so that $K$ is generated by the $b_{1,n}$. But it is also easy to see that $b_{1,n}$ lies in the subgroup generated by $b_{1,n+1}$. Since $G$ is polycyclic (Mark showed this in his answer, when he showed $G$ is a quotient of the Klein bottle group), $K$ is finitely generated, and this gives us enough to conclude $K$ is cyclic. Now in writing $G=K\rtimes\mathbb{Z}$, the $\mathbb{Z}$ factor is generated by $y_0$. Quotienting out by $y_0^2$ gives the dihedral group $D_{2p}$, and thus $K$ must have order $p$, so that $G=C_p\rtimes\mathbb{Z}$.