Debes de crear un arreglo con todas las letras del abecedario q hay en tu base de Datos , algo asi:
select substring(nombre,1,1) from tabla
group by substring(nombre,1,1)
order by substring(nombre,1,1) asc
Luego debes de crear otro recordset donde guardes tus registro ordenandos , al final solo imprimes tu arreglo de letras como links para tu paginacion.
Espero te ayude en algo