We report nuclear magnetic resonance studies on the beta-pyrochlore oxide superconductor KOs2O6. The nuclear relaxation at the K sites is entirely caused by fluctuations of the electric field gradient, which we ascribe to highly anharmonic low frequency oscillation (rattling) of K ions. A phenomenological analysis shows a crossover from overdamped to underdamped behavior of the rattling phonons with decreasing temperature and its sudden sharpening below the superconducting transition temperature T-c. Suppression of the Hebel-Slichter peak in the relaxation rate at the O sites below T-c also indicates strong electron-phonon coupling.