What is the meaning of Maximum Expected Differential/Linear Probability (MEDP/MELP)? I was reading this paper which has a lot of references to the terms MEDP and MELP. Even though i think i got the general meaning, I could not verify that it is indeed correct.

For the MEDP, I would say that it is the maximum bias that can be achieved over k rounds of encryption.

For the MELP, respectively, I would say that is the maximum probability of an equation that holds over k rounds of encryption.

And both are used in order to evaluate the resistance of an encryption scheme against differential and linear cryptanalysis, for example by setting the upper bounds on those metrics.
Is that right?

Also, I have noticed that those quantities are referred for 2 rounds of encryption in a lot of cases. (is various AES MEDP,MELP papers)
Is there a particular reason why they choose only 2 rounds, or it's just matter of computational complexity?
The paper you link to gives precise definitions for the MEDP and MELP.  I will attempt to explain the definitions more expansively &amp; clearly.

First, the differential probability (DP) function with respect to a given block cipher takes an input difference $\Delta x$, an output difference $\Delta y$, and a key $k$ as inputs and generates a probability as the output.  This probability can be understood to mean: “the number of pairs of plaintexts $(P_a, P_b)$ such that $P_a \oplus P_b =  \Delta x$ and $E_k(P_a) \oplus E_k(P_b) = \Delta y$ (where $E_k(\cdot)$ is the encryption function of the given blockcipher under the key $k$) divided by the total number of possible pairs of plaintexts where $P_a \oplus P_b =  \Delta x$ (which is just $2^B$ where $B$ is the block-size in bits of the blockcipher).”

The Expected Differential Probability (EDP) is a function that takes an input difference and output difference and finds the simple average DP of that input-output difference pattern (averaged over all possible keys).  Expectation in this case reduces to the simple average because as the paper states we are assuming all keys are equiprobable.  So in plain English, add up the DP of that difference pattern for every key and then divide the resulting sum by the size of the keyspace (e.g. $2^{128}$ for AES-128).

The MEDP is simply the maximum such EDP over all possible pairs of input difference and output difference, excluding the all-zero input/output difference (which if not excluded would trivially be the maximum, but which is not useful for cryptanalysis).  In (hopefully) plainer English, this asks what pattern of input and output differences gives the attacker the best chance (averaged over all keys) of finding a pair of plaintexts that match that pattern, and how much of a chance is that best chance?

The MEDP is used to evaluate how resilient a block cipher is to differential cryptanalysis.  If you can prove that a cipher has a very low MEDP then the cipher is provably secure against that type of attack (“very low” meaning something only slightly higher than the MEDP of a random permutation, i.e. $\dfrac{1}{2^B}$).

Switching to the linear probability (LP), with respect to a given block cipher this is a function that takes an input mask $a$ (a string of bits $B$ long), an output mask $b$, and a key $k$ and returns a probability.  In terms of how these masks are used, $a \bullet X$ means taking the $B$-bit string $a$ and ANDing it with the $B$-bit string $X$, and then xoring together all $B$ bits of the resulting string to get a checksum bit.  As section 5 of the paper describes, the probability generated by the LP function is: $2 \cdot$ “number of plaintext-ciphertext pairs $(P_i, E_k(P_i))$ for which $a \bullet P_i = b \bullet E_k(P_i)$ divided by the total number of possible plaintexts (i.e. $2^B$)” $-1$ all squared.  For example, if the expression $a \bullet P_i = b \bullet E_k(P_i)$ is true for exactly half of the possible plaintexts $P_i$ then the LP would be $(2 \cdot \frac{1}{2} -1)^2 = 0^2 = 0$.  If the number of plaintexts for which the expression is true deviates from 50% (either higher or lower than 50%) then the LP will be higher than 0, and the more the deviation the closer the LP will get to 1.

The ELP is very similar to the EDP in that for a particular pair of input and output masks the ELP gives the average LP (averaged over all possible equiprobable keys).  Like the MEDP, the MELP is simply the maximum ELP over all possible input-output mask pairs (excluding the all zero masks).  Similar to the MEDP, the MELP is used to evaluate how resilient a block cipher is to linear cryptanalysis (a provably very low MELP is a proof that the cipher is secure against that type of attack).

For the last part of your question, the reason why the paper focuses so much on finding the exact MEDP and MELP for 2 rounds of AES is that one can prove that the MEDP and MELP for 4 (or more) rounds of AES is upper bounded by the 2-round MEDP (respectively MELP) raised to the power 4.  So if they find the 2-round MEDP/MELP they immediately can give an upper bound on the MEDP/MELP of the entire cipher.