Suggested solution
Maybe just try to use TextBox instead of a Label and bind Text instead of Content. You can find example of the binding here: How to format TimeSpan in XAML. It's also worth noticing that TextBlock is more lightweight then Label, so it should be used when possible.
Alternative solutions
If you want to use Label for some reason, there seems to be a property called ContentStringFormat of a Label itself, so your xaml can look like:
<Label Content="{Binding ElementName=Root, Path=DataSource.TimeTotal}" ContentStringFormat="hh\\:mm"/>
Another solution would be implementing a custom IValueConverter, where you can pass string format as converter's parameter and format the value manually in the converter's code. This solution should then work correctly for all appropriate control types. More about value converters can be found here and here.
String formatting properties
As Erode wrote in the comment, there seem to be other controls for which StringFormat does not work.
However, for controls derived from ContentControl you should be able to use ContentStringFormat and for controls derived from ItemsControl, there is a ItemStringFormat property. There is a link with few samples presenting how to use those:
http://blogs.msdn.com/b/llobo/archive/2008/05/19/wpf-3-5-sp1-feature-stringformat.aspx