Paint, Photoshop, Paint Shop Pro, Gimp... hay multitud de programas donde escoger el que mejor te sirve para realizar los graficos.
Creo que tienes una pequeña confusion con los nombres:
- backgrounds
suelen ser los graficos que se posicionan en la parte posterior de la pantalla, digamos el "fondo"
- tile maps
son graficos construidos a partir de otros graficos mas pequeños y combinables entre si. Se suelen gestionar mediante programacion para crear graficos en tiempo de ejecucion. Una vez tengas el grafico (mas conocido como 'tile') tan solo necesitas crearte una rutina grafica que gestione su muestra por pantalla las veces y posiciones que te interesan. Pero eso ya es otra historia, depende de la programacion que hagas del juego.
Por ejemplo si quieres tener un juego con un bosque puedes hacerlo con un solo grafico que ya sea todo el bosque completo (background) o construir el bosque uniendo pequeños graficos de arboles (tile maps). Obviamente debes escoger segun tus necesidades y las ventajas que te aporte cada opcion segun su consumo de recursos.