Example methods and apparatus to form secure cross-VPN (virtual private network) communication sessions in multiprotocol label switching (MPLS)-based networks are disclosed. An example method comprises sending a first border gateway protocol route advertisement to a first provider edge router associated with a first one of two multiprotocol label switched-based virtual private networks in response to receiving a cross-virtual private network link setup request from an application server, the route advertisement comprising a flow-spec parameter, and the setup request identifying a communication path between two user devices associated with the first and second multiprotocol label switched-based virtual private networks, sending a second border gateway protocol route advertisement to a second provider edge router associated with the second multiprotocol label switched-based virtual private network, and restricting a communication session between the two user devices of the first and second multiprotocol label switched-based virtual private networks to a first protocol for a threshold period of time based on a restriction parameter shared by the communication path.