Does our current notion of velocity/acceleration (based on calculus) require absolute time? When people explain special relativity, they say that a velocity in one frame leads to time dilation in that frame relative to a stationary frame.
When we say something like $v=\mathrm{d}x/\mathrm{d}t$ or $a=\mathrm{d}v/\mathrm{d}t$. Isn't dt something that cannot change? A smallest infinitesimal unchanging amount. Newton described it in terms of absolute space and time. 
How does it make sense to define a velocity of one frame as $\mathrm{d}x/\mathrm{d}t$ yet say that the rate of time itself changes?
Can $\mathrm{d}t$ change?
 A: 
Isn't dt something that cannot change?

In Special Relativity, time $t$ is a coordinate rather than a (universal) parameter.
To locate an event in spacetime in a particular reference frame, one must specify 4 coordinates, 3 spatial and 1 temporal.
So, a quantity like $\frac{dx}{dt}$ is a coordinate velocity; it is the rate of change of one coordinate with respect to another.
But coordinates are not absolute so, in Special Relativity, coordinate velocity and coordinate acceleration are relative, i.e., they depend on the coordinate system one chooses.
Now, the worldline of an object - the object's locus of events in spacetime - is absolute.  And, a parameter of the worldline is the proper time $\tau$, the time according to a clock stationary with respect to (carried along with) the object.
So, one can take the derivative of the coordinates of an object with respect to the proper time, e.g., $\frac{dx}{d\tau}$ where $d\tau$ is invariant, i.e., the same in all coordinate systems.
For example, the quantity $\frac{d\vec x}{d\tau}$ is called the proper velocity, $\vec w$, of the object.
In addition, we have the change in coordinate time with respect to proper time, $\frac{dt}{d\tau} = \gamma$ where
$$\gamma = \frac{1}{\sqrt{1 - \frac{v^2}{c^2}}}, v= |\frac{d\vec x}{dt}| $$
Thus, we have
$$\vec w = \frac{d\vec x}{d\tau} =  \frac{d\vec x}{dt}\frac{dt}{d\tau} = \gamma \vec v$$
A: The operation that seems to be causing you confusion is called a boost. A boost is an operation on minkowski space-time that in many ways is analagous to a rotation in three dimensional space. So let's make sure we understand the analogous situation dealing with rotations in three dimensional space.
Rotations
Let's imagine we have a stick which has a length $L$. Let's suppose we are in some coordinate system where the stick is in the $z$-$x$ plane, and it makes an angle $\theta$ with the $x$ axis. Then let's denote by $L_x$ the projection of its distance along the $x$-axis. Then $L_x = L \cos \theta$. Notice that you can also think of $\theta$ in terms of the relationship $\tan \theta = \frac{L_z}{L_x}$. This last form is similar to defining an (average) $x$-velocity to be $\frac{dx}{dt}$.
Now let's suppose we do a rotation by changing our axis so that the stick makes a smaller angle $\phi$ with the $x$-axis. We will find a very curious result: we find that $L_x$ has somehow gotten longer. Also if we look at $\frac{L_z}{L_x} = \tan \theta$, we find that it too has changed.
Now does this mean that we couldn't have defined $\theta$ in the first frame? No, of course we can define angles. It's just that the change when we change frames.
Boosts
Now let's think about boosts. We have some space-time interval described by some $\Delta t$ and $\Delta x$. There is an average velocity $v=\frac{\Delta x}{\Delta t}$. This is no harder to define than an angle in space. 
Now suppose we do a boost. This looks similar to a rotation and $\Delta t$ and $\Delta x$ will both change, and their quotient $v=\frac{\Delta x}{\Delta t}$ will also change. But this is fine. It is just like how our $\theta$ changed when we did a rotation. 
So to answer your question, yes it does make sense to define velocities in minkowski space, just as much as it makes sense to define angles in euclidean space. And yes $\mathrm{d} t$ does change when you do a boost, but that is expected, and consistent with the fact that the speed changes. 
