Atomic ensembles have many potential applications in quantum information science. Owing to collective enhancement, working with ensembles at high densities increases the overall efficiency of quantum operations, but at the same time also increases the collision rate and markedly changes the time dynamics of a stored coherence. We study theoretically and experimentally the coherent dynamics of cold atoms under these conditions. A closed form expression for the spectral line shape is derived for discrete fluctuations in terms of the bare spectrum and the Poisson rate constant of collisions, which deviates from the canonical stochastic theory of Kubo. We measure a prolongation of the coherence times of optically trapped rubidium atoms as their density increases, a phenomenon we call collisional narrowing in analog to the well known motional narrowing effect in NMR. We explain under what circumstances collisional narrowing can be transformed into collisional broadening. On account of collisions, conventional echo techniques fail to suppress this dephasing, and multi-pulse dynamical decoupling sequences are required. We present experiments demonstrating a 20-fold increase of the coherence time when a sequence with more than 200 pi pulses is applied. We perform quantum process tomography and demonstrate that using the decoupling scheme a dense ensemble with an optical depth of >200 can be used as an atomic memory with coherence times exceeding 3 sec. Further optimization requires utilizing specific features of the collisional bath, which we measure directly.