Routing of nets is one of the most time consuming steps in the FPGA design flow. While existing works have described ways of accelerating the process through parallelization, they are not scalable. In this paper, we propose a scalable way of parallelizing the routing algorithm through Lagrangian relaxation. The FPGA routing problem is formulated as a linear programming problem, and the channel width constraints, which limit the amount of parallelism, are relaxed by incorporating them into the objective function. The result of the relaxation yields independent sub-problems that we solve using minimum Steiner tree algorithms. Our approach outperforms the state-of-The-Art FPGA parallel router by producing an average self-relative speedup of 7.05X with 8 threads, reduces the total wire length by 22.4%on average and has similar channel width requirements as VPR, albeit at the cost of 7.5%longer critical path. Another advantage of our algorithm is that the number of threads and the order in which the nets are routed has totally no impact on the quality of result.