We present new high-resolution (R~14,000) spectra of the two brightest HeII-transparent quasars in the far-UV (FUV) at z>3.5, HE2QSJ2311-1417 (z=3.70) and HE2QSJ1630+0435 (z=3.81), obtained with the Cosmic Origins Spectrograph (COS) on the Hubble Space Telescope (HST). In the predominantly saturated HeII absorption spectra, both sightlines show several isolated resolved (full width at half maximum FWHM>50 km/s) transmission spikes in HeII Ly$alpha$ and HeII Ly$beta$. The incidence of such spikes decreases with increasing redshift, but both sightlines show significant spikes at z>3.5, signaling the presence of fully ionized regions in the z>3.5 intergalactic medium (IGM). We employ an automated algorithm to compare the number of detected HeII transmission spikes to predictions from mock spectra created from the outputs of a cubic (100/h cMpc)^3 optically thin Nyx hydrodynamical simulation, assuming a range of UV background photoionization rates $Gamma_mathrm{HeII}$. From the incidence of Ly$alpha$ and Ly$beta$ transmission spikes we infer similar photoionization rates of $Gamma_mathrm{HeII}=2.0^{+0.6}_{-0.5}times 10^{-15}$s$^{-1}$ at 3.51<z<3.66 and $Gamma_mathrm{HeII}=0.9pm0.3 times 10^{-15}$s$^{-1}$ at 3.460<z<3.685, respectively. Because the transmission spikes indicate fully ionized regions at z>3.5 along both lines of sight, our observations provide further evidence that HeII reionization had substantially progressed at these redshifts.