gdal_translate will work using the -srcwin or -projwin options.
-srcwin xoff yoff xsize ysize:
Selects a subwindow from the source image for copying based on pixel/line location.
-projwin ulx uly lrx lry: Selects a subwindow from the source image
for copying (like -srcwin) but with the corners given in georeferenced
coordinates.
You would need to come up with the pixel/line locations or corner coordinates and then loop over the values with gdal_translate. Something like the quick and dirty python below will work if using pixel values and -srcwin is suitable for you, will be a bit more work to sort out with coordinates.
import os, gdal
from gdalconst import *
width = 512
height = 512
tilesize = 64
for i in range(0, width, tilesize):
for j in range(0, height, tilesize):
gdaltranString = "gdal_translate -of GTIFF -srcwin "+str(i)+", "+str(j)+", "+str(tilesize)+", " \
+str(tilesize)+" utm.tif utm_"+str(i)+"_"+str(j)+".tif"
os.system(gdaltranString)