The method joro suggests works with little change for any $(k,m)$.
Fix an elliptic curve $E: P(X,Y)=1$ of positive rank. Some simple examples are $F(X,Y) = Y^2 - X^3 + 2X$ and $F(X,Y) = Y^2 - X^3 - 2$, each with generator $(X,Y)=(-1,1)$.
Let $u$ and $v$ be "random" rational functions on $E$ that generate the function field (almost any choice will work, see below). Then $u$ and $v$ satisfy a minimal equation $g(u,v)=0$ which defines an algebraic curve birational to $E$ and thus has infinitely many rational solutions.
Set $x = u^k$ and $y = v^m$. As long as these functions, too, generate the function field of $E$, the equation $f(x,y)=0$ that they satisfy gives an irreducible elliptic curve with infinitely many rational points at which $x$ is a $k$-th power and $y$ is an $m$-th power. To check this it is enough to verify that the map $(X,Y) \mapsto (x,y) = (u^k,v^m)$ is generically injective on $E$, and for that it's enough to find one point $(u,v)$ on $E$ that's not a zero or pole of either $u$ or $v$ and such that there's no other $(u',v') \in E$ with ${u'}^k=u^k$ and ${v'}^m = v^m$. For some $k$ and $m$ we can even take $(u,v) = (X,Y)$, and in general a pair of "random" translates $(X+u_0, Y+v_0)$ should suffice.
The polynomial equation $f(x,y) = 0$ can be computed by eliminating $u,v$ from the system $g(u,v) = u^k-x = v^m-y = 0$: take the resultant of the first two equations with respect to $u$ to obtain a relation between $v$ and $x$, and then take the resultant w.r.t. $v$ of that relation and $v^m-y$.
For example, applying this recipe to $Y^2 = X^3 + 2$ with $(k,m)=(11,7)$ and $(u,v)=(X,Y)$ can be done with the gp command
polresultant(polresultant(Y^2-X^3-2, X^11-x, X), Y^7-y, Y)
which yields the irreducible polynomial
x^21 + (-36960y^2 + 14336)x^18 + (154y^6 + 396506880y^4 + 19029491712y^2 + 88080384)x^15 + (12029248y^8 - 1216366964736y^6 + 284451691560960y^4 - 391801278038016y^2 + 300647710720)x^12 + (5236y^12 + 41292382208y^10 + 649374955536384y^8 + 261188560760078336y^6 + 4032263773430480896y^4 + 1338427807910330368y^2 + 615726511554560)x^9 + (-61949888y^14 + 5483890384896y^12 - 20842181162958848y^10 + 8440505090430730240y^8 - 456851090435200778240y^6 + 2810028717064564244480y^4 - 898304588698945060864y^2 + 756604737398243328)x^6 + (16016y^18 + 1301780480y^16 + 5890099511296y^14 + 5689217111818240y^12 + 1688064484691673088y^10 + 172250320914033410048y^8 + 5873494991874845310976y^6 + 55086593993714775883776y^4 + 78432673497651496353792y^2 + 516508834063867445248)x^3 + (-y^22 + 1408y^20 - 901120y^18 + 346030080y^16 - 88583700480y^14 + 15874199126016y^12 - 2031897488130048y^10 + 185773484629032960y^8 - 11889503016258109440y^6 + 507285462027012669440y^4 - 12986507827891524337664y^2 + 151115727451828646838272)
vanishing on infinitely many pairs $(x,y) = (X^{11},Y^7)$.