We present the results of an ongoing investigation to provide a detailed view of the processes by which massive stars shape the surrounding interstellar medium (ISM), from pc to kpc scales. In this paper we have focused on studying the environments of Wolf-Rayet (WR) stars in M31 to find evidence for WR wind-ISM interactions, through imaging ionized hydrogen nebulae surrounding these stars. We have conducted a systematic survey for HII shells surrounding 48 of the 49 known WR stars in M31. There are 17 WR stars surrounded by single shells, or shell fragments, 7 stars surrounded by concentric limb brightened shells, 20 stars where there is no clear physical association of the star with nearby H-alpha emission, and 4 stars which lack nearby H-alpha emission. For the 17+7 shells above, there are 12 which contain one or two massive stars (including a WR star) and that are <=40 pc in radius. These 12 shells may be classical WR ejecta or wind-blown shells. Further, there may be excess H-alpha point source emission associated with one of the 12 WR stars surrounded by putative ejecta or wind-blown shells. There is also evidence for excess point source emission associated with 11 other WR stars. The excess emission may arise from unresolved circumstellar shells, or within the extended outer envelopes of the stars themselves. In a few cases we find clear morphological evidence for WR shells interacting with each other. In several H-alpha images we see WR winds disrupting, or punching through, the walls of limb-brightened HII shells.