Interesting link from David Hembrow - the Dutch do manage to do it cheaper
http://www.aviewfromthecyclepath.com/2009/11/costings-of-improvements-for-cyclists.html
€200k for 0.4 km of cycle track on both sides of the road, plus sorting out all the pipes, electric at the same time (fancy that!).