I think the problem you might have on the route that you have described, is it is during the wet season. Last wet season those roads from Maur' to Mali were impassbale for long periods of time. That doesn't mean it will be the same this August, but it should be in your planning.
I have never been to Mali, but I know Guinea Bissau very well (I use to live there). I was there visiting in March 2003, drove from Senegal and highly recommend it. However, it will be the wet season and the roads will be in very bad condition. In Bissau good accommodation is expensive and the power & water are off more times than they are working.
Try to get out to the outer islands, as they are just great. You can drive form Bissua around to Boloma Island, 8-10 hours, and there should be a car ferry to take you across the channel to Boloma. It is a great place. All other islands you will need to get a ferry from Bissau, which can be difficult. Mainly because of maintenance problems etc.
If you require any more info on Bissau or Senegal let me know.