In a small saucepan, combine sugar and water. Heat over high until mixture boils and sugar dissolves completely. Remove from heat, add mint, and steep 10 minutes.
While the mint leaves steep, chop up about half of a large watermelon into small cubes. Measure 8 generous cups of cubed watermelon and using a blender or food processor, blend until smooth. There will be seeds and pulp in the blended watermelon- that's fine.
Remove mint leaves from simple syrup mixture and discard. Pour syrup into blended watermelon and stir to combine. Using a fine mesh sieve, strain watermelon mixture to separate pulp from juice. Pour juice into a 10x7 inch pan and freeze.
After 3 hours, mix granita with a fork. It should begin to freeze and this will help it keep its slushy texture. Freeze at least 3 more hours until frozen. To serve, take granita out of the freezer and set on the counter for 10 minutes. Flake granita mixture with a fork and serve with a sprig of mint on top.