We present a Distributed Memory Parallel (DMP) implementation of agent-based economic models, which facilitates large-scale simulations with millions of agents. A major obstacle in scalable DMP implementation is to distribute a balanced workload among MPI processes, while making all the topological graphs, over which the agents interact, available at a minimum communication cost. We addressed this problem by partitioning a representative employer-employee interaction graph, and all the other interaction graphs are made available at negligible communication costs by mimicking the organizations of the real-world economic entities. Cache-friendly and low-memory intensive algorithms and data structures are proposed to improve runtime and scalability, and the effectiveness of each is demonstrated. The current implementation is capable of simulating 1:1 scale models of medium-sized countries.