Propagation of relativistically intense azimuthally or radially polarized laser pulses (RPP) in underdense plasmas is demonstrated to be unstable, via 3D particle-in-cell simulation and disregarding the Kerr non-linearity. Strong pulse filamentation occurs for RPP in transversely uniform plasma with an increment, $Gamma$, close to the well-known one depending on acceleration, $alpha$, and modulated density gradient length, $L$, as $Gamma approx (alpha/L)^{1/2}$. In deep plasma channels the instability vanishes. Electron self-injection and acceleration by the resulting laser pulse wake is explored.