Each update can be done in $O(\lg n)$ time, by using a balanced binary tree data structure.
Let $F$ denote the set of points in the Pareto frontier. Store $F$ in a balanced binary tree, using the $x$-coordinate of each point as its key.
Now, given a new point $(x_q,y_q)$, you can check whether it is Pareto-dominated by any element of $F$ by finding the first element of $F$ to the right of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \ge x_q$ and $x$ is minimal); then checking whether it dominates $(x_q,y_q)$. If not, you can check whether $(x_q,y_q)$ dominates any element of $F$ by finding the first element of $F$ to the left of $(x_q,y_q)$ (i.e., the element $(x,y) \in F$ such that $x \le x_q$ and $x$ is as large as possible), and checking whether $(x_q,y_q)$ dominates it. Then, you can use that information to decide whether you need to add $(x_q,y_q)$ to $F$ and whether there is any existing element of $F$ that needs to be deleted.
All of this can be done in $O(\lg n)$ time, using a balanced binary tree data structure.
This works in 2 dimensions (i.e., 2-tuples). In higher dimensions, the problem gets much harder. You can find references to the literature, with techniques for higher dimensions, at How to find a subset of potentially maximal vectors (of numbers) in a set of vectors but I'm afraid that in high dimensions, all the known algorithms are likely to be fairly slow (they have a factor that is something like $O((\lg n)^{d-1})$ where $d$ is the number of dimensions).