With an increasing number of machine-type communication devices (MTCDs), machine-to-machine (M2M) communications have attracted great attentions from both academia and industry. Different from traditional communication networks, the data connections with M2M communications are typically small-sized but with high frequency, necessitating the efficiency optimization of both energy consumption and computation. In this paper, we introduce mobile edge computing (MEC) into virtualized cellular networks with M2M communications, to decrease the energy consumption and optimize the computing resource allocation as well as improve computing capability. Moreover, based on different functions and quality of service (QoS) requirements, the physical network can be virtualized into several virtual networks, and then each MTCD selects the corresponding virtual network to access through the embedded-SIM (eSIM) technology. Meanwhile, the random access process of MTCDs is formulated as a partially observable Markov decision process (POMDP) to minimize the system cost, which consists of both the energy consumption and execution time of computing tasks. Furthermore, to facilitate the network architecture integration, software-defined networking (SDN) is introduced to deal with the diverse protocols and standards in the networks. Extensive simulation results with different system parameters reveal that the proposed scheme could significantly improve the system performance compared to the existing schemes.