This is one of those question where solid answer is not an easy one to follow. This function is powered by Walker_Page class and you can replace it with your own walker (extended from Walker_Page or just Walker) by passing its name in walker argument to wp_list_pages().
In a nutshell it is very highly flexible way to do it, but not very convenient and easy to grasp, especially when not messing with walkers regularly.