Rutherglen to carstairs has flat crossings at Newton, Uddingston, Motherwell, shieldmuir, law and lanark. The 400 figure is what the current estimate for HS2 is. Finding a clear route from Rutherglen isn't going to be easy or cheap as thers not much that has a suitable alignment for high speed. Would a better option be reinstating 4 tracks north from uddingston and from Sheildmuir into Motherwell with grade separated junctions at Law and Sheildmuir. Not sure much could be done at motherwell or uddingston and Newton isnt as much of a problem since the links were double tracked.
As soon as you're touching the existing railway the costs skyrocket. This is what Network Rail and the DfT have been finding out to their cost over the past several years. A totally new line might look excessive but it massively simplifies the job - e.g. you can work year-round rather than scheduling everything for specific bank holiday or seasonal blockades.
The Greengauge 21 report seems to neglect a very important thing. There's simply no point spending billions on cutting minutes off journey times when trains will end up queuing to get through Haymarket. The biggest consistent peak-time journey time savings can be made by bypassing the busiest sections of track. The basic concept of a new line into Glasgow does that quite well - it would rejoin the Central approach tracks after Rutherglen so that there wouldn't be any conflicting movements or slow services in the way. For Edinburgh the only way to do it would be to build a third pair of heavy rail tracks heading westwards from Waverley. It would be a big job but it would be transformational, enabling significant numbers of new local and regional services to run. A tunnel from Princes Street Gardens out to the City Bypass, with an interchange station at Edinburgh Park, would make all sorts of InterCity services more useful. Sure, you'd lose out on a Haymarket call, but for the wider city region having the second Edinburgh station accessible directly from the trunk road network would be a huge boon. Someone living in Prestonpans might be able to get a heavy rail train into Waverley and then change onto an express service, but someone living out in (say) Loanhead would be stuck on the roads heading into the very centre of the city.
Such a tunnel would definitely take all Edinburgh-Carlisle express traffic, and future Edinburgh to Glasgow expresses too. Whether it would be useful to add a chord up to the Fife lines would be another question. The western tunnel wouldn't be able to call at Haymarket, and that's going to be a more useful destination for internal Scottish traffic than it is for Anglo-Scottish. The E&G services would lose out Haymarket but gain a stop at the bypass for the various business development areas from Edinburgh Park up to the Airport, would have a faster and more reliable route into Waverley for the city centre, and there would still be plenty of regional services still calling there so it balances out.