M dwarfs are favorable targets for exoplanet detection with current instrumentation, but stellar companions can induce false positives and inhibit planet characterization. Knowledge of stellar companions is also critical to our understanding of how binary stars form and evolve. We have therefore conducted a survey of stellar companions around nearby M dwarfs, and here we present our new discoveries. Using the Differential Speckle Survey Instrument at the 4.3 m Lowell Discovery Telescope, and the similar NN-EXPLORE Exoplanet Stellar Speckle Imager at the 3.5 m WIYN telescope, we carried out a volume-limited survey of M-dwarf multiplicity to 15 parsecs, with a special emphasis on including the later M dwarfs that were overlooked in previous surveys. Additional brighter targets at larger distances were included for a total sample size of 1070 M dwarfs. Observations of these 1070 targets revealed 26 new companions; 22 of these systems were previously thought to be single. If all new discoveries are confirmed, then the number of known multiples in the sample will increase by 7.6%. Using our observed properties, as well as the parallaxes and 2MASS K magnitudes for these objects, we calculate the projected separation, and estimate the mass ratio and component spectral types, for these systems. We report the discovery of a new M-dwarf companion to the white dwarf Wolf 672 A, which hosts a known M-dwarf companion as well, making the system trinary. We also examine the possibility that the new companion to 2MASS J13092185-2330350 is a brown dwarf. Finally, we discuss initial insights from the POKEMON survey.