Iodine-doped graphene has recently attracted significant interest as a result of its enhanced conductivity and improved catalytic activity. Using density functional theory calculations, we obtain the formation energy, desorption rate, and electronic properties for graphene systems doped with polyiodide chains consisting of 1-6 iodine atoms in the low-concentration limit. We find that I-3 and I-5 act as p-type surface dopants that shift the Fermi level 0.46 and 0.57 eV below the Dirac point, respectively. For these two molecules, molecular orbital theory and analysis of the charge density show that doping transfers electronic charge to iodine pi* molecular orbitals oriented perpendicular to the graphene sheet. For even-length polyiodides, we find that I-6 and I-4 decompose to I-2, which readily desorbs at 300 K. Adsorption energy calculations further show that I-3 acts as an effective catalyst for the oxygen reduction reaction on graphene by stabilizing the rate-limiting OOH intermediate.