Hi Ishan,
I had a similar issue. What solved this problem for me was using the neo4j-admin import tool to create both, nodes and relationships, at the same time. Here are the docs: Import - Operations Manual
Creating millions of nodes was not a problem for me using APOC or LOAD CSV. However, the APOC functions were taking more than 6 hours to create the relationships between a subset of 300,000 nodes.
If you're already working in Python, then creating the csv files for the neo4j-admin import tool should not be too difficult. Pandas was pretty much all I needed for this and the neo4j-admin import tool took about 30 minutes to create all of my nodes and relationships.
I hope this helps. Best of luck.
-Tony