The transition from gasoline-powered vehicles (GVs) to electric vehicles (EVs) is crucial for promoting green transportation. However, this transition poses challenges for mobility service providers (MSPs) due to increased operational costs. Motivating MSPs to adopt EVs and minimizing the negative impact on the urban transportation system requires effective strategies. Government agencies (Govs) commonly employ market-oriented instruments (e.g., carbon cap-and-trade schemes) and non-market-oriented instruments (e.g., the installment of emission reduction devices for GVs) to address emission reduction goals. In response to the Gov emission reduction policies, MSPs must decide whether to (i) replace their GVs with EVs and (ii) install emission reduction devices and purchase emission quotas for their GVs. The dynamics of emission quota supply and demand further influence equilibrium carbon prices in the carbon market. To capture the complex interactions between MSPs and the Gov, we propose a bilevel optimization model. Building upon this model, we consider two extensions: First, MSPs have the flexibility to adjust the number of operating vehicles. Second, there are heterogeneous MSPs, with some exclusively owning EVs and others owning GVs. Analytical findings reveal that MSPs benefit from replacing GVs with EVs only when the cost of EV replacement is less than or equal to the monetary benefit obtained by selling excess emission quotas in the carbon market. Moreover, as the Gov imposes stricter regulations, the EV replacement rate is more likely to increase, while the cumulative number of operating vehicles decreases, which ultimately passes on the emission reduction costs to travelers.