We present a scheme for joint sparse-channel recovery and data detection in cyclic-prefix orthogonal frequency division multiplex (CP-OFDM) communication over doubly-spread underwater acoustic channels. Inter-carrier-interference (ICI), caused by path-dependent Doppler, results in a non-diagonal channel mixing matrix that makes recovery difficult. To combat the effect of ICI, we consider the sequence of observations from partial interval demodulators, and using a path-based channel model, cast them into a data model amenable for sparse channel recovery. We then propose a two-stage algorithm for joint channel estimation and data detection. In the first stage, we recover the channel from pilot only observations and estimate the unknown data symbols from post-combined partial interval demodulator outputs. In the second stage, we use the data symbols estimated in the first stage to reconstruct the dictionary matrix corresponding to a full interval demodulator, re-estimate the channel using the entire observations including data subcarriers, and use it to detect the unknown data symbols. We also iterate between channel estimation and data detection in each stage, refining the dictionary in every iteration, to further reduce the detection error. Our simulation studies show that initial sparse channel recovery from the outputs of partial-interval demodulators considerably improves data detection performance, in terms of bit error rate, over that from a traditional full length demodulator output, in highly doppler distorted scenarios.