From memory in 2008:
Dakar to Kaolack good (bar crazy traffic in Dakar).
Kaolack to Kidira starts getting potholed but generally good speed.
Kidira to Tambacounda is a real mess, more potholes than tar, though they were working on it.Took 6 hours in a truck.
Manager of Simenti Lodge in Niokolo Koba nat park told me that everything is so expensive there because nobody wants to drive from Dakar to Tamba beause of that poor section of road. It may well have improved by now, but it was pretty poor between Kidira and Tambacounda in march 2008.
From the Senegal Mali border to Bamako is perfect. Road finished, in really good shape. Stop at the Fort de Medine about 10km from kayes, a lovely spot by the river and some waterfalls.