If you are happy with booking Advance fares and be tied to specific trains, then you may wish to try the following split points: Cheltenham Spa, Birmingham New Street, Preston and / or Carlisle.
The split at Cheltenham Spa is to take advantage of CrossCountry's weird pricing strategy, where longer-distance passengers tend to be the ones ripped off. You will find plenty of availability between Bristol Temple Meads and Cheltenham Spa for £4.70 each way, then between Cheltenham Spa and Birmingham for £6.90 each way, but booking through tickets from Bristol to Birmingham only gives you options for £15.50 each way generally speaking.
The split at Preston/Carlisle is to take advantage of lower fares (generally speaking) available on TPE from there onwards to/from Scotland, as opposed to just Virgin. The lowest through fare on Virgin or CrossCountry between Birmingham and Edinburgh comes out at £35 for the outward, and £25 for the return leg. By splitting Advances, Birmingham - Preston has more availability for £15 outward, £10/£11 return (even one in the morning for £7.50), while Preston - Edinburgh has plenty of availability under £15 outward and around £10 return.
I won't list all the permutations but hopefully just by doing the above, you can see for yourself how many possibilities there are, and pick the timings that suit you. It might mean a slightly extended journey time, especially at Preston where you are likely to have to change trains, but I hope the saving is worth it.
A sample itinerary which I think offers a reasonable trade-off between time and savings is:
17th March
Bristol Temple Meads 1030 - Cheltenham Spa 1109 £4.70
Cheltenham Spa 1111 - Birmingham New Street 1158 £6.90 (same train, remain onboard at Cheltenham)
Birmingham New Street 1215 - Preston 1351 £15
Preston 1458 - Edinburgh 1736 £11.20
18th March
Edinburgh 1416 - Preston 1649 £11.20 £11.20
Preston 1717 - Birmingham Temple Meads 1905 £10
Birmingham New Street 1942 - Cheltenham Spa 2024 £6.90
Cheltenham Spa 2025 - Bristol Temple Meads 2105 £4.70 (same train, remain onboard at Cheltenham)
Total: £70.60
Obviously I cannot guarantee that this is the absolute cheapest, and that these fares are sold subject to quota so you need to act quickly if you want to snap them up.
I must stress that if you wish to book split tickets, you must ensure that you leave sufficient interchange time at the stations where you change trains, in order to be covered in the event of delays. This is 12 minutes for Birmingham New Street, 5 minutes for Cheltenham Spa, 8 minutes for Carlisle, and 8 minutes for Preston. If you require information for other stations then feel free to ask.